TREES

Defining Trees
Trees
Trees are used in applications in which the relation between
data elements needs to be represented in a hierarchy.
A tree is a finite set of one or more nodes such that
There is a specially designated node called the root
The remaining nodes are partitioned into n>=0 disjoint sets T 1,…..Tn
where each of these sets is a tree. T1,…..Tn are called subtrees of
root.
It is a nonlinear data structure

B C D

E F G H I J K

L M
Defining Trees (Contd.)
Each element in a tree is referred to as a node.

The topmost node in a tree is called root.

root

B C D

E F G H I J K

L M node
Defining Trees (Contd.)

Each node in a tree can further have subtrees below its

hierarchy.
root

B C D

E F G H I J K

L M node
Tree Terminology

Leaf/Terminal node: It refers to a node with no children.

A
Nodes E, F, G, H, I, J,
L, and M are leaf nodes.
B C D

E F G H I J K

L M
Tree Terminology (Contd.)
Children of a node: The roots of the subtrees of a node are
called the children of the node.
Subtree: A portion of a tree, which can be viewed as a
separate tree in itself is called a subtree.
A subtree can also contain just one node called the leaf node.

A
Tree with root B,
containing nodes
B C D E, F, G, and H is
a subtree of node
A.
E F G H I J K
E, F, G, and H are
children of node B.
L M B is the parent of
these nodes.
Tree Terminology
Edge: A(Contd.)
link from the parent to a child node is referred to as
an edge.
Degree of a node: It refers to the number of subtrees of a
node in a tree.
Degree of tree: Maximum degree ‘d’ of nodes in the tree

A
Degree of node C is 1
Degree of node D is 2
B C D Degree of node A is 3
Edge Degree of node B is 4

E F G H I J K

L M
Siblings/Brothers: It refers to the children of the same node
Ancestor:- Ancestors of a node are all the nodes along the path
from root to that node
Descendant:- All nodes in the path from a given node to a leaf node
Right Descendant: - Node N2 is right descendant of N1 if node N2
is either the right son of N1 or descendant of right son of N1.
Left Descendant: - Node N2 is left descendant of N1 if node N2 is
either the left son of N1 or descendant of left son of N1.

A Nodes B, C, and D are

siblings of each other.
Nodes E, F, G, and H are
B C D
siblings of each other.

E F G H I J K

L M
Tree Terminology (Contd.)
Internal node: It refers to any node between the root and a
leaf node.
Level of a node: It refers to the distance (in number of
nodes) of a node from the root. Root always lies at level 1.
As you move down the tree, the level increases by one.

Level 1
A

Level 2
B C D

E F G H I J K Level 3

L M Level 4

Nodes B, C, D, and K are

internal nodes.
 • Depth of a node is a length of path from root to that node
Tree Terminology (Contd.)
The depth of the k following tree is 2

• Height: The height of the tree is the maximum level of any

node in the tree

Level 1
A

Level 2
B C D

E F G H I J K Level 3

L M Level 4
Just a minute
Consider the following tree and answer the questions that
follow:
a. What is the depth of the tree?
b. Which nodes are children of node B?
c. Which node is the parent of node F?
d. What is the level of node E?
e. Which nodes are the siblings of node H?
f. Which nodes are the siblings of node D? root
g. Which nodes are leaf nodes?
A

B C

D E F G

H I
Just a minute

Answer:
a. 3
b. D and E
c. C
d. 2
e. H does not have any siblings
f. The only sibling of D is E
g. F, G, H, and I
Defining Binary Trees Binary Tree
A binary tree is a tree in which no node can have more than
two subtrees
A node can have zero, one or two subtrees. These subtrees
are designated as the left subtree & right subtree
Each subtree is itself a binary tree

B C

D E F

H
G
 Cont’
Left Skewed Binary Tree Right Skewed Binary Tree

The binary tree doesn't have right The binary tree doesn't have left
subtree. subtree.

 The maximum no of nodes on level i of a binary tree is 2 i-1 i≥1 or 2i i≥0

 The maximum no of nodes in a binary tree of depth k is 2 k-1 k≥1 or 2k+1-1 k≥0
Defining Binary Trees

Strictly binary tree:

A binary tree in which every non leaf node has non-empty left
and right children.
Defining Binary Trees (Contd.)

Full binary tree:

A full binary tree of depth k is a binary tree of depth k
having 2k+1-1 nodes (k>=1) i.e. the max no of nodes
such a binary tree can have

A
Depth = 2
Total number of
3
nodes = 2 – 1 = 7
B C

D E F G
Defining Binary Trees (Contd.)
Complete binary tree:
A complete binary tree of depth k is a tree with n node in which these n
nodes can be numbered sequentially from 1 to n as if it would have been
the first n nodes in a full binary tree of depth k

1 1 1
A A A

2 B 3 C 2 B 3 C 2 B 3 C

4 5 6 7 4 5 6 4 5 6
D E F G D E F D E G

Full Binary Tree Complete Binary Tree Incomplete Binary Tree

 Conversion of General Tree to Binary Tree
• Can use two relationships:
– parent to child
– sibling to sibling

• Steps:
i. Identify the branch from the parent to its first or left most child

ii. Connect siblings, starting with the leftmost child, using a branch for
each sibling to its right sibling

iii.Remove all unneeded branches from the parent to its children

 Example

General Tree

Binary Tree
 Binary Tree Representation
Representing a Binary Tree

Sequential/ Array representation of binary trees:

Nodes are numbered from 1 to n. We can use a one
dimensional array to store the nodes
a) parent of i is at i/2 if ≠ 1. if i=1, is at the root & has no parents
b) leftchild(i) is at 2i
c) rightchild(i) is at 2i+1
 Binary Tree

1 2 3 4 5 6 7 8 9 10 11

A B C D E F G - - H I

Array representation of binary Tree

 Cont’d
• Limitation :
– If binary tree is not a complete binary tree, then it
leads to the wastage of storage
– Not suitable for frequent insertion and deletion
Binary Tree Representation
Linked representation of a binary tree:
It uses a linked list to implement a binary tree.
Each node in the linked representation holds the following
information:
Data
Reference to the left child
Reference to the right child
If a node does not have a left child or a right child or both, the
respective left or right child fields of that node point to NULL.

Leftchild Data Rightchild

Node
Representing a Binary Tree (Contd.)

root root

52
. 52 .

36 68 . 36 . 68 .

24 59 72 24 59 . 72 .

70 80 . 70 80

Binary Tree Linked Representation

 Class for Tree
class treenode class tree
{
{
treenode * root;
int data;
treenode * maketree();
treenode * lchild, * rchild; public:
public: tree()
friend class tree; {
treenode() root = NULL;
}
{
void create()
data = 0 ; lchild = NULL;
{
rchild = NULL; root = maketree();
} }
}; };
treenode* tree::maketree()
cout<<”Enter left child ?(y/n):”;
{
cin>> ch;
treenode * temp;
if (ch=='y')
char ch;
temp→lchild=maketree();
temp= new treenode;
return temp;
cout<<”enter data”;
}
cin>>temp→data;
int main()
cout<<”Enter right child ?(y/n):”;
{
cin>>ch;
tree t;
if (ch=='y')
t.create();
temp→rchild=maketree();
}
Non-Recursive creation of Binary Tree
class treenode
class tree
{
{
private:
private:
int data;
treenode * root, * p;
treenode * lchild, * rchild;
queue q;
public:
int ch;
friend class tree;
treenode *maketree();
friend class queue;
public:
treenode()
void setleft(treenode *p);
{
void setright (treenode *p);
data = 0 ;
void create();
lchild = NULL;

rchild = NULL; void insert();

}}; };
class queue{
treenode* del()
private:
{
int r,f;
f++
treenode *q[25];
return q[f];
public:
}
queue()

{ int empty()

r=f=-1; {

} if((r==-1 || (f>=r))

void add(treenode *p) return 1;

{ else
r++; return 0;
q[r]=p;
}
}
};
treenode * tree :: maketree() else
{
{
p →lchild=maketree();
treenode *p; q.add (p →lchild);
}
p=new treenode;
}
cout<< “enter data” void tree :: setright(treenode *p)

cin>> p→data; {

return p; if (p →rchild!=NULL)

} cout<<”invalid insertion”;

void tree ::setleft (treenode *p) else

{ {

if (p →lchild!=NULL) p →rchild=maketree();

cout<<”invalid insertion”; q.add (p →rchild);

}}
void tree :: create() cin>> ch;

{ if(ch==1)

root=maketree(); setleft(p);

q.add(root); cout<<”Do you want to insert right child

of “<< p→data;
}
cin>> ch;
void tree :: insert ()
if(ch==1)
{
setright(p);
while(q.empty()==0)
}
{
}
p=q.del();

cout<<”Do you want to insert left child

of “<< p→data;
 Binary search tree
• A binary search tree is a binary tree with the following properties:
– All items in the left subtree are less than the root

– All items in the right subtree are greater than or equal to the root

– Each subtree is itself a binary search tree

50

30 60

25
40 70

35 65
2
Create BST for following data: 67, 18, 3, 55, 62,
80, 96, 12, 38
Insert 67
67 Insert 18

Insert 3

18 80 Insert 55

Insert 62

Insert 80
3 55 96
Insert 96
Insert 12
Insert 38
12 38 62
 else
procedure CreateBST(data)
child = parent ->rlink;
{
}
if(root == NULL)
if(data == child->data && child!=NULL)
root = new treenode(data)
print “Duplicate data”
else
elseif(data < parent->data)
{
parent->llink = new treenode(data);
parent = child = root
else
while(child!=NULL &&child->data! =data)
parent->rlink = new treenode (data);
{
}
parent = child;

if(data < parent->data)

child = parent ->llink;

 Deletion of Node from Binary Search Tree
• Deletion of node with no child
– Set the delete node’s link in the parent to null, free its memory and return
 Deletion of a Node with one child
 If there is only a right subtree, then simply attach the right subtree to the delete
node’s parent and free its memory
 If there is only a left subtree, then simply attach the left subtree to the delete node’s
parent and free its memory
 Deletion of a Node with Two Children
 Find the largest node in the deleted node’s left subtree and move its data to replace
the deleted node’s data

OR

 Find the smallest node in the deleted node’s right subtree and move its data to
replace the deleted node’s data
 Binary Tree Traversals
• Requires each node of the tree be processed once & only once
in a predetermined sequence.
• Two approaches to the traversal sequence
– Depth first traversal
– Breadth first traversal

• Depth First Traversal:

– We process all of the descendants of a child before going on to the
next child
– Following are the three standard depth first traversal
a) Preorder traversal
b) Inorder traversal
c) Postorder traversal
 INORDER TRAVERSAL

• Moving down the tree toward the left until you can go no
further
• Visit the node
• Move one node to the right & continue
• If you cannot move to the right, go back one more node
RECURSIVE INORDER TRAVERSAL
procedure inorder(Treenode *T)

if (T==NULL)

return;

call inorder (T→lchild)

print (T→data)

call inorder (T→rchild)

}
 NON-RECURSIVE INORDER TRAVERSAL
Procedure inorder(Treenode *T )
{
while(1)
{
while(T ≠ NULL)
{
s.push(T);
T=T→lchild;
}//end while
if(s.empty())
return;
T=s.pop();
print T→data;
T = T→rchild;
} //end while
}
 PREORDER TRAVERSAL
• Moving down the tree toward the left until you can go no further
• Visit the node
• Move one node to the right & continue
• If you cannot move to the right, go back one more node
 Recursive Preorder Traversal
procedure preorder(Treenode *T)

if (T == NULL)

return;

print (T→data)

call preorder (T→lchild)

call preorder (T→rchild)

end preorder
NON-RECURSIVE PREORDER TRAVERSAL
Procedure preorder(Treenode *T )

while(1){

while(T ≠ NULL)

print T → data;

if (T→rchild!=NULL)

s.push(T→rchild)

T=T→lchild;

} //end while

if(s.empty())

return;

T=s.pop();

} //end while

}
 Postorder Traversal
 Moving down the tree toward the left until you can go no further
 Move one node to the right & continue
 Visit the node
 If you cannot move to the right, go back one more node
 Recursive Postorder Traversal
procedure postorder(T)

if (T ==NULL)

return;

call postorder (T→lchild)

call postorder (T→rchild)

print (T→data);

end postorder
procedure postorder(Treenode *T)
T=T→lchild
{
} //end while
Treenode *temp;

temp = new node('-1’); if (stack.empty())

while(1) return;
{ while(!stack.empty())
while (T ≠ NULL) {
{
p=stack.pop();
stack.push(T);
if(p==temp)
if (T→rchild!=NULL)
break;
{

stack.push(T→rchild);
else

stack.push(temp); print p→data;

} //end if } //end while

If(!stack.empty())

T = stack.pop();

} //end while

}
 Breadth First Traversal
procedure BFS(T) if (root →rchild!=NULL)

{ Q.add(root→rchild)

root=T if (Q.empty()==0)
root=Q.del();
while (root!=NULL)
else
{
root=null;
print root→data
}
if (root →lchild!=NULL) }
Q.add(root→lchild)
 Mirror Image of Binary Tree
procedure swaptree(p)

if (p==NULL)

return ;

swaptree(p→llink);

swaptree(p→rlink);

temp=p→llink;

p→llink=p→rlink;

p→rlink=temp;

end swaptree
treenode* copy(treenode *p) procedure leaf (treenode *p)
{
{
if(p==NULL)
return p; if(p==NULL)
treenode * root= new node; return;
root->data=p->data;
leaf (p→llink);
root->left=copy(p->llink);
root->right=copy(p->rlink); leaf (p→rlink);
return root; if (p→rlink==NULL && p→llink==NULL)
}
print p→data;
}
end leaf
procedure height(treenode *p)

int x=0,y=0;

if(p==NULL)

return 0;

x=height(p→llink);

y=height(p→rlink);

if(x>y)

return x+1;

else

return y+1;

}end height
Create tree from pre-order & post-order traversal

1. Root of the tree is the first element in the preorder sequence. Marks as x
2. The root of the right subtree of x is the predecessor of x in the postorder.
Marks as y.
3. Find the occurrence of y in the preorder sequence, all the nos after y will
be on the right subtree.
4. The root of the left subtree of x is the successor of x in the preorder.
Marks as z.
5. Find the occurrence of z in the postorder sequence, all the nos before z
will be on the left subtree.
6. Repeat steps 2 to 5 to find roots and subtree recursively
 Issues in Binary Tree
 Binary tree with n nodes have n+1 null links.
 Wastage of memory because of null links.
 Extra storage space for stack and queues since recursion is required to traverse the
tree completely.
 Difficult to find successor node for a given node
 Threaded Binary Tree
 Utilize null fields in such a way so that the empty left child of a node points
to its inorder predecessor and empty right child of the node points to its
inorder successor in inorder traversal.

 Left threaded binary tree

 Right threaded binary tree
 Full threaded binary tree
 Left Threaded Binary Tree
• A thread will appear in a left field of a node and will point
to the predecessor node in the inorder traversal

Fig: Left threaded binary tree

 Right Threaded Binary Tree
• A thread will appear in a right field of a node and will point to
the next or successor node in the inorder traversal

Fig: Right threaded binary tree

 Full Threaded Binary Tree
• A thread will appear in the left and right field of a node and
will point to the preceding node and successor node the any
order traversal

Fig: Full threaded binary tree

 Cont’d
Advantages:
Reduce time complexity of algorithm
General operations like traversal, insertion and deletion can be done without using recursive
algorithm
Easy to find inorder successor of any node ‘n’ in a threaded binary tree

Linked list representation of TBT

Llink Lbit Data Rbit Rlink

For thread Lbit=Rbit=0

For link Lbit=Rbit=1

To avoid loose thread, a head node is used in threaded binary tree
The tree is the left subtree of the head node

0 - 1
 Huffman Code
• Huffman Coding is a famous Greedy Algorithm.
• It is used for the lossless compression of data.
• It uses variable length encoding.
• It assigns variable length code to all the characters.
• The code length of a character depends on how frequently it
occurs in the given text.
• The character which occurs most frequently gets the smallest
code.
• The character which occurs least frequently gets the largest
code.
• It is also known as Huffman Encoding.
 Building a Huffman tree
• Find frequencies of each symbol occurring in message
• Begin with a forest of single node trees
– each contain symbol and its frequency
• Do recursively
– select two trees with smallest frequency at the root
– produce a new binary tree with the selected trees as
children and store the sum of their frequencies in the
root
• Recursion ends when there is one tree
– this is the Huffman coding tree
 Example
• Build the Huffman coding tree for the message
This is his message
• Character frequencies
A G M T E H _ I S
1 1 1 1 2 2 3 3 5

• Begin with forest of single trees

1 1 1 1 2 2 3 3 5
A G M T E H _ I S
 Step 1

1 1 1 1 2 2 3 3 5
A G M T E H _ I S
 Step 2

2 2

1 1 1 1 2 2 3 3 5
A G M T E H _ I S
 Step 3

2 2 4

1 1 1 1 2 2 3 3 5
A G M T E H _ I S
 Step 4

2 2 4

1 1 1 1 2 2 3 3 5
A G M T E H _ I S
 Step 5

2 2 4 6

1 1 1 1 2 2 3 3 5
A G M T E H _ I S
 Step 6

4 4

2 2 2 2 6

E H

1 1 1 1 3 3 5
A G M T _ I S
 Step 7

8 11

4 4 6 5
S

2 2 2 2 3 3

E H _ I

1 1 1 1
A G M T
 Step 8
19

8 11

4 4 6 5
S

2 2 2 2 3 3

E H _ I

1 1 1 1
A G M T
 Label edges
19
0 1

8 11
0 1
0 1

4 4 6 5
0 1 0 1 0 1 S

2 2 2 2 3 3
0 1 0 1 E H _ I

1 1 1 1
A G M T
 Huffman code & encoded message
This is his message

S 11
E 010
H 011
_ 100
I 101
A 0000
G 0001
M 0010
T 0011

00110111011110010111100011101111000010010111100000001010
 Applications
• Data compression for communication
• Saves transmission time because it is variable
length encoding system
 Expression Tree
• An expression tree is a binary tree +
with the following properties
– Each leaf is an operand
– The root and internal nodes are * D
operators
– Subtrees are subexpressions with the
root being an operator
A +
• The hierarchical precedence and
associativity rules of the operators
in terms of the expressions are
B C
reflected in the orientation of the
subtrees or the sibling nodes.
Expression Tree for
A*(B+C)+D
 Three standard traversal
• Infix
• Postfix
• Prefix

• To print infix expression tree, add an opening

parenthesis at the beginning and closing at the end of
each expression.

• For preorder and postorder parenthesis is not required.

procedure infix(T)
{
if (T==NULL)
{
if(T->token is an operand)
print t->token
else
{
print(open parenthesis)
infix(T->left)
print(T->token)
infix(T->right)
print(close parenthesis)
}
}
}