Data Structure Arora Educator
Arora Educator
Topic : Trees
✓ Non-linear data structure
Arora Educator
Topic : Trees
Arora Educator
Trees
✓ Organizing a data in hierarchical
fashion / non linear fashion.
✓ Without having closer loop.
✓ All elements of tree are
represented as = Nodes (as linked
list)
Arora Educator
Trees Terminology
1) Nodes = Contains data
2) Root = Top Node Arora Educator
3) Parent Node = Have Child Arora Educator
4) Child Node Arora Educator
5) Siblings = Same Parent Arora Educator
6) Leaf Node/ External Node = No child
Arora Educator
7) Internal Node = Minimum 1 child Arora Educator
8) Edge = Connection b/w Nodes Arora Educator
9) Degree of Node = Number of child Arora Educator
Degree of leaf node is always 0
9) Degree of Node = Number of child Arora Educator
Degree of node A = 2
Degree of node B = 3
Degree of node C = 2
Degree of node D = 0
Degree of node E = 2
Degree of node F = 0
Degree of node G = 1
Degree of Tree = Max Child Degree of node H = 0
Degree of node I = 0
=3 Degree of node J = 0
In the binary tree degree of Degree of node K = 0
tree is always = 2
10) Depth of Node / Level = Total Arora Educator
number of edges from root node to
a particular node (Longest path)
✓ Depth of the root node = 0 Depth of Tree = 3
10) Depth of Node / Level Arora Educator
Depth of node A = 0
Depth of node B = 1
Depth of node C = 1
Depth of node D = 2
Depth of node E = 2
Depth of node F = 2
Depth of node G = 2
Depth of node H = 2
Depth of node I = 3
Depth of node J = 3
Depth of node K = 3
11) Height of tree = Arora Educator
Height of Tree = 3
11) Height of Node = Arora Educator
longest path from the node to a leaf
node
11) Height of Node = Arora Educator
longest path from the node to a leaf
node
Types of Tree Data Structure = 4
1) General tree Arora Educator
2) Binary tree (5 Types)
3) Binary search tree
4) Balanced tree
Other Tree
✓ AVL Tree
✓ Red Black Tree
✓ B Tree = Self Balanced Tree
Types of Tree Data Structure = 4
1) General Tree = Parent node can Arora Educator
have any number of child nodes.
Types of Tree Data Structure = 4 Arora Educator
2) Binary Tree =
✓ Maximum/atmost nodes = two
child (left & right)
✓ Nodes possible = 0,1,2
✓ Root Node = Top Node
✓ No children Node = Leaf Node
Types of Tree Data Structure = 4 Arora Educator
Extended Binary Tree =
✓ every node has either zero or
two children
✓ 0 Child = External Nodes
✓ 2 Children = Internal Nodes
Types of Tree Data Structure = 4 Arora Educator
3) Binary Search Tree =
✓ Value of the left node is = less than
its parent
✓ Value of the right node is = more
than its parent
Types of Tree Data Structure = 4 Arora Educator
3) Binary Search Tree =
✓ left node = less
✓ right node is = more
Types of Tree Data Structure = 4 Arora Educator
4) Balanced Tree =
✓ height of the left sub-tree and the
right sub-tree is equal
or
✓ difference between the height of the
left subtree and right subtree is not
more than 1
5 Types of Binary Tree Arora Educator
1) Full/Proper/Strict = 0 or 2 Child
2) Complete = All Levels fill, except last
3) Perfect = All Levels fill
4) Degenerate/ Skewed = Left or Right
5) Balanced = Already discuss
1- Full/Proper/Strict Binary Tree Arora Educator
0 or 2 child
2- Complete Binary Tree Arora Educator
All the levels of the tree are filled completely
except the lowest level nodes
2- Complete Binary Tree Arora Educator
3- Perfect Binary Tree Arora Educator
All level of the tree is completely filled by the
nodes
4- Degenerate Binary Tree Arora Educator
✓ Also called Skewed Binary Tree
✓ Skewed to the left or right
4- Degenerate Binary Tree Arora Educator
5- Balanced Binary Tree Arora Educator
✓ height of the left sub-tree and the right
sub-tree is equal
or
✓ difference between the height of the left
subtree and right subtree is not more than
1
