data structures and algorithms

DATA STRUCTURE http://www.youtube.com/c/EDULINEFORCS
STUDENT




MODULE 4
TREES & GRAPHS




Prepared By Mr. EBIN PM, AP, IESCE 1




TREE
• A tree is a nonlinear data structure. Data elements are related in a
hierarchal manner (parent-child relationship)
• The first node of the tree is called Root node.
• Final nodes are called Leaf nodes.
• Leaf nodes are also called terminal nodes.
• A child has a single parent but a parent has more than one
children. So we can say that , here, a one to many relationship is
exist.
• In a general tree, A node can have any number of children nodes
but it can have only a single parent.
Prepared By Mr.EBIN PM, AP, IESCE EDULINE 2




Prepared By Mr. EBIN PM, AP, IESCE

,DATA STRUCTURE http://www.youtube.com/c/EDULINEFORCS
STUDENT




• The following image shows a tree, where the node A is the root
node of the tree while the other nodes can be seen as the children
of A.

1




2




3



Prepared By Mr.EBIN PM, AP, IESCE EDULINE 3




BASIC TERMINOLOGY
Root node - topmost node in the tree hierarchy
Sub tree - If the root node is not null, the tree T1, T2 and T3 is called
sub-trees of the root node.
Degree – The number of sub trees of a node. Eg: The degree of A is 3
Siblings - Children of the same parent. Eg: G, H are the siblings of D
Level – If a node is at level l, then its children are at level l+1
Depth – The height or depth of a tree is defined to be the maximum
level of any node in the tree
Forest – If we remove the root of a tree , we get a forest. Eg: If we
remove A, we get a forest with 3 trees.
Prepared By Mr.EBIN PM, AP, IESCE EDULINE 4




Prepared By Mr. EBIN PM, AP, IESCE

,DATA STRUCTURE http://www.youtube.com/c/EDULINEFORCS
STUDENT




Prepared By Mr.EBIN PM, AP, IESCE EDULINE 5




BINARY TREE
• A binary tree is either empty or consist of a root and 2 disjoint
binary trees called the Left Sub tree and Right Sub tree .

• Each node can have at most two children
• B is the left child of A
• C is the right child of A




Prepared By Mr.EBIN PM, AP, IESCE EDULINE 6




Prepared By Mr. EBIN PM, AP, IESCE

, DATA STRUCTURE http://www.youtube.com/c/EDULINEFORCS
STUDENT




TYPES OF BINARY TREE
Strictly Binary Tree – All nodes must have a left child and a right
child except leaf node

• Here B, F , G & E are leaf nodes




Prepared By Mr.EBIN PM, AP, IESCE EDULINE 7




Skewed Binary Tree - It is a special kind of binary tree. Two type
skewed binary trees are Left skewed and Right skewed




• Full Binary Tree - If each node of binary tree has either two
children or no child at all, is said to be a Full Binary Tree. Full binary
tree is also called as Strictly Binary Tree.
Prepared By Mr.EBIN PM, AP, IESCE EDULINE 8




Prepared By Mr. EBIN PM, AP, IESCE