Trees

Tree
 Tree is a derived, Non-Linear data structure base on
 Directed, Acyclic Graph
 Where the in-degree for each node can be 0/1
 Out-degree is n
A

 Root – Indegree 0 B C D
 Leaf/External – outdegree 0
 Internal node – outdegree is E F G

is non-zero
Basic Terminology
Root node The root node Ris the topmost node in the tree. If R = NULL, then it means the
tree is empty.
Sub-trees If the root node Ris not NULL, then the trees T1, T2,and T3 are called the sub-
trees of R.
Leaf node A node that has no children is called the leaf node or the terminal node.
Path A sequence of consecutive edges is called a path. For example, in Fig. 9.1, the path
from the root node Ato node Iis given as: A, D, and I.
Ancestor node An ancestor of a node is any predecessor node on the path from root to that
node. The root node does not have any ancestors. In the tree given in Figure, nodes A, C, and
G are the ancestors of node K.
Descendant node A descendant node is any successor node on any path from the node to a
leaf node. Leaf nodes do not have any descendants. In the tree given in Figure, nodes C, G,
J, and Kare the descendants of node A.
Level number Every node in the tree is assigned a level number in such a way that the root
node is at level 0, children of the root node are at level number 1. Thus, every node is at one
level higher than its parent. So, all child nodes have a level number given by parent’s level
number + 1.
Degree of a node is equal to the number of children that a node has. Degree The degree of a
leaf node is zero.
In-degree In-degree of a node is the number of edges arriving at that node.
Out-degree Out-degree of a node is the number of edges leaving that node.
 Types of Trees
1. General trees
2. Forests
3. Binary trees
4. Binary search trees
5. Expression trees Forest and its corresponding tree Binary tree

Parent If N is any node in T that has left successor S1 and right successor S2, then N is called the parent
of S1and S2. Correspondingly, S1and S2 are called the left child and the right child of N.
Sibling All nodes that are at the same level and share the same parent are called siblings(brothers).
Edge It is the line connecting a node Nto any of its successors. A binary tree of n nodes has exactly n – 1edges
because every node except the root node is connected to its parent via an edge.
Path A sequence of consecutive edges. For example, in Figure, the path from the root node to the node 8 is
given as: 1, 2, 4, and 8.
Depth The depth of a node N is given as the length of the path from the root R to the node N. The depth of the
root node is zero.
Height of a tree It is the total number of nodes on the path from the root node to the deepest node in the tree. A
binary tree of height hhas at least hnodes and at most 2h – 1 nodes
 Similar binary trees Two binary trees T and T’ are said to be similar if both these
trees have the same structure.
 Copies Two binary trees T and T’ are said to be copies if they have similar structure
and if they have same content at the corresponding nodes

Similar binary trees Copies

Tree Classification
 Unary tree
 Binary Tree
 Ternary Tree
 N-ary Tree

Unary Binary Tree

Ternary Tree
Binary Tree
Strictly B. T. Almost Complete B. T. Complete B. T.

A A A

B C B C B C

D E D E F D E F G

Binary Search Tree Heap Tree

5 9

3 7 3 8

2 4 6 9 2 1 6 5
Linked list representation
5
L 5 R

3 7

NULL
L 3 L 7 R
2 6 9

NULL
NULL

NULL

NULL

NULL

NULL
2 6 9

typedef struct tree

{
int info;
struct tree *left, *right;
} tnode;

tnode *root = NULL;

Linked list representation
Representation of Tree using Array

• Root is always at the beginning 3 7

• Left child is at 2*i

• Right Child is at 2*i + 1 2 6 9

Where ‘i’ is index of parent

•For any given child ‘i’, its parent 1 2 3 4 5 6 7 8 9

is located at i/2 location. 5 3 7 2 6 9

 int main( )
void create(int tree[]) {
{ int tree[20]={0}, i;
int n,val,i,k; create(tree);
printf("no. of nodes:"); for(i=1;i<20;i++)
scanf("%d",&n); printf("%d ",tree[i]);
printf("Enter the values of each node:"); }
for(k=1;k<=n;k++)
{
scanf("%d",&val);
i=1;
while(tree[i]!=0)
{
if(val < tree[i])
i = 2 * i;
else
i = 2 * i + 1;
}
tree[i]=val;
}
}
Traversal
 Inorder
 Left, root, right
5
2, 3, 5, 6, 7, 9
3 7

 Postorder
2 6 9
 Left, right, root
 2, 3, 6, 9, 7, 5

 Preorder
 Root, left, right
 5, 3, 2, 7, 6, 9
Give the inorder, preorder andpostorder traversal
void inorder(int tree[],int root)
{
if(tree[root]!=0) void preorder(int tree[],int root)
{ {
inorder(tree,2*root); if(tree[root]!=0)
printf("%d ",tree[root]); {
inorder(tree,2*root +1);
}
printf("%d ",tree[root]);
} preorder(tree,2*root);
preorder(tree,2*root +1);
void postorder(int tree[],int root) }
{ }
if(tree[root]!=0)
{
postorder(tree,2*root);
postorder(tree,2*root +1);
printf("%d ",tree[root]);
}
}
 Constructing a Binary Tree from Traversal
Steps to construct the Binary tree given the in-order and pre-order traversal:

• Use the pre-order sequence to determine the root node of the tree. The first element
would be the root node.
• Elements on the left side of the root node in the in-order traversal form the left sub-tree
of the root node. Similarly, elements on the right side of the root node in the in-order
traversal form the right sub-tree of the root node.
• Recursively select each element from pre-order traversal sequence and create its left
and right sub-trees from the in-order traversal sequence.

Steps to construct the Binary tree given the in-order and post-order traversal:

• In post-order traversal the root node is the last node. Rest of the steps will be the same
as mentioned above
Constructing Tree given preorder and inorder

A X

S E M R

T Q D C F
Constructing Tree given preorder and inorder

A X

S E M R

T Q D C F
Constructing Tree given postorder and inorder
void create() void inorder(tnode *root)
int main( )
{ {
{
tnode *newnode, *temp, *prev; if(root!=NULL)
create();
int k,n; {
printf("\n");
printf("no. of nodes:"); inorder(root->left);
inorder(root);
scanf("%d",&n); printf("%d ",root->info);
printf("\n");
printf("Enter the values of each node:"); inorder(root->right);
postorder(root);
for(k=1;k<=n;k++) }
printf("\n");
{ }
preorder(root);
newnode = (tnode*) malloc (sizeof(tnode));
void postorder(tnode *root) getch();
newnode->left=newnode->right=NULL;
{ }
scanf("%d", &newnode->info);
if(root==NULL) if(root!=NULL)
root=newnode; {
else postorder(root->left);
{ postorder(root->right);
temp=root; printf("%d ",root->info);
while(temp!=NULL) }
{ }
prev=temp; void preorder(tnode *root)
if(newnode->info < temp->info) {
temp = temp->left; if(root!=NULL)
else {
temp = temp->right; printf("%d ",root->info);
} preorder(root->left);
if(newnode->info < prev->info) preorder(root->right);
prev->left = newnode; }
else }
prev->right = newnode;
}
}
}
 Binary Search Trees
A binary search tree, also known as an
ordered binary tree, is a variant of
binary trees in which:
• all the nodes in the left sub-tree have
a value less than that of the root node
and
• all the nodes in the right sub-tree
have a value either equal to or greater
than the root node.
• The same rule is applicable to every
sub-tree in the tree.

NOTE: Since the nodes in a binary

(a) Left skewed BST
search tree are ordered, the time needed
to search, insert and delete an element in (b) right skewed BST
the tree is greatly reduced.
Create a binary search tree using the following data elements:
45, 39, 56, 12, 34, 78, 32, 10, 89, 54, 67, 81
 Searching in a Binary Search Tree
Search for 62

78

65 85

53 68 81 89

45 62 72 87 92
 Inserting a node in a Binary Search Tree
Inserting 48

78

65 85

53 68 81 89

45 62 72 87 92

48
 Deleting a node from a Binary Search Tree

There are three different cases:

• Deleting a Node that has No Children Eg: 62
• Deleting a Node with One Child Eg. 68
• Deleting a Node with Two Children Eg. 85 78

65 85

53 68 81 89

45 62 72 87 92
 Deleting a node from a Binary Search Tree

Deleting a Node that has No Children Eg: 62

Before After
78
78

65 85
65 85

53 68 81 89
53 68 81 89

45 72 87 92
45 62 72 87 92
 Deleting a node from a Binary Search Tree

Deleting a Node with One Child Eg. 68

Before After
78
78

65 87
65 85

53 72 81 89
53 68 81 89

45 92
45 62 72 87 92
 Deleting a node from a Binary Search Tree

Deleting a Node with Two Children Eg. 85

Before After
78
78

65 85
65 85

53 72 81 89
53 68 81 89

45 87 92
45 62 72 87 92
Deleting a node from a Binary Search Tree
Expression Tree
 Binary tree representing the Arithmetic expression.
 Internal nodes are operators and external nodes represent operands
 Example:

a+b Can be split as +

+
a b

a b
Expression Tree
 A+B*C–D/E
–
 A + T1 – D / E
 A + T1 – T2 T2
/
T3
+
 A + T1 – T2
 T3 – T2 D E
A T1
*
 T4

B C
 Try this
1. P + Q * (R – S) + T
2. A + B / C * D – E
Construction of Expression Tree
For every symbol of Postfix expression do
a) Construct a node and initialize left and right to NULL
b) If the symbol is operand, then, store that in newnode and push on to
the stack
c) If the symbol is operator, then,
a) Newnode->right = pop( )
b) Newnode->left = pop( )
c) Newnode->info = symbol
d) Push (newnode)
At the end, top of the stack contains root node.
 Given an expression, Exp = ((a + b) – (c * d)) % ((e ^f) / (g – h)),
construct the corresponding binary tree.
((a + b) – (c * d)) % ((e ^f) / (g – h))
( T1 – T2 ) % ( T3 / T4)
T5 % T6
T7
Given the binary tree, write down the expression that it represents

[{(a/b) + (c*d)} ^ {(f % g)/(h – i)}]

tnode *stack[10]; void inorder(tnode *root)
int top = -1; { int main( )
void push(tnode *op) if(root!=NULL) {
{ { char postfix[20];
stack[++top]=op; inorder(root->left); printf("Enter the postfix
} printf("%c ",root->info); expression:");
inorder(root->right); scanf("%s",postfix);
tnode* pop() } create(postfix);
{ } printf("\n");
return(stack[top--]); inorder(root);
} void postorder(tnode *root)
printf("\n");
void create(char postfix[]) {
postorder(root);
{ if(root!=NULL)
printf("\n");
tnode *newnode; {
preorder(root);
int i; postorder(root->left);
getch();
for(i=0;postfix[i]!='\0';i++) postorder(root->right);
}
{ printf("%c ",root->info);
newnode = (tnode*) malloc (sizeof(tnode)); }
newnode->left=newnode->right = NULL; }
newnode->info = postfix[i]; void preorder(tnode *root)
if(isalpha(postfix[i])) {
push(newnode); if(root!=NULL)
else {
{ printf("%c ",root->info);
newnode->right = pop(); preorder(root->left);
newnode->left = pop(); preorder(root->right);
push(newnode); }
} }
}
root = pop();
}
 Evaluating Expression Tree
float eval(tnode *root)
21
–
{
float op1, op2;
21
+ 2
/
if(isdigit(root->info))
return(root->info);
1 20
* 6 3
else
{
5 4
op1=eval(root->left);
op2=eval(root->right);
return(calc(op1,root->info,op2);
}
}
Binary Search Tree Sorting
 Construct Binary search Tree
 Perform Inorder traversal – Sorted list
(Left – Root – Right)

100

10 50 80 100 130 150 200

50 150

10 80 130 200
Threaded Binary Tree
 In a linked representation of a binary tree, the number
of null links (null pointers) are actually more than non-
null pointers.
 Consider the following binary tree:
Threaded Binary Tree
 In above binary tree, there are 7 null pointers & actual 5
pointers.
 In all there are 12 pointers.
 We can generalize it that for any binary tree with n nodes
there will be (n+1) null pointers and 2n total pointers.
 The objective here to make effective use of these null
pointers.
 A. J. perils & C. Thornton jointly proposed idea to make
effective use of these null pointers.
 According to this idea we are going to replace all the null
pointers by the appropriate pointer values called threads.
Threaded Binary Tree
 And binary tree with such pointers are called threaded
tree.
 In the memory representation of a threaded binary tree,
it is necessary to distinguish between a normal pointer
and a thread.
Threaded Binary Tree
 Therefore we have an alternate node representation for
a threaded binary tree which contains five fields as
show bellow:
Threaded Binary Tree
 Alsoone may choose a one-way threading or a two-way
threading.
 Here,our threading will correspond to the in order
traversal of T.
Threaded Binary Tree - One-Way

 Accordingly, in the one way threading of T, a thread

will appear in the right field of a node and will point to
the next node in the in-order traversal of T.
 See the bellow example of one-way in-order threading.
Threaded Binary Tree: One-Way
Inorder of bellow tree is: D,B,F,E,A,G,C,L,J,H,K
One Way Threaded Binary Trees
Threaded Binary Tree - Two-Way

 In the two-way threading of T.

 A thread will also appear in the left field of a node and will
point to the preceding node in the in-order traversal of tree T.
 Furthermore, the left pointer of the first node and the right
pointer of the last node (in the in-order traversal of T) will
contain the null value when T does not have a header node.
Threaded Binary Tree
 Bellow figure show two-way in-order threading.
 Here, right pointer=next node of in-order traversal and
left pointer=previous node of in-order traversal
 Inorder of bellow tree is: D,B,F,E,A,G,C,L,J,H,K
Threaded Binary Tree
Two way Threaded Binary Trees
Threaded Binary Tree
Two-way Threading with Header node

 Again two-way threading has left pointer of the first node

and right pointer of the last node (in the inorder traversal of T)
will contain the null value when T will point to the header
nodes is called two-way threading with header node threaded
binary tree.
Threaded Binary Tree
 Bellow figure to explain two-way threading with header node.
Threaded Binary Tree
 Bellow example of link representation of threading binary tree.
 In-order traversal of bellow tree: G,F,B,A,D,C,E
Two way Threaded Binary Trees with header Node
Threaded Binary Tree
 Advantages of threaded binary tree:
 Threaded binary trees have numerous advantages over non-
threaded binary trees listed as below:
The traversal operation is more faster than that of its
unthreaded version, because with threaded binary tree non-
recursive implementation is possible which can run faster
and does not require the botheration of stack management.
Threaded Binary Tree
 Advantages of threaded binary tree:
 The second advantage is more understated with a threaded binary
tree, we can efficiently determine the predecessor and successor
nodes starting from any node. In case of unthreaded binary tree,
however, this task is more time consuming and difficult. For this
case a stack is required to provide upward pointing information in
the tree whereas in a threaded binary tree, without having to
include the overhead of using a stack mechanism the same can be
carried out with the threads.
Threaded Binary Tree
 Advantages of threaded binary tree:
 Any node can be accessible from any other node. Threads are
usually more to upward whereas links are downward. Thus in a
threaded tree, one can move in their direction and nodes are in
fact circularly linked. This is not possible in unthreaded counter
part because there we can move only in downward direction
starting from root.
 Insertion into and deletions from a threaded tree are although
time consuming operations but these are very easy to implement.
Threaded Binary Tree
 Disadvantages of threaded binary tree:
Insertion and deletion from a threaded tree are very
time consuming operation compare to non-threaded
binary tree.
This tree require additional bit to identify the threaded
link.