Data Structures and Applications (CS204) Module 4

Module 4

Trees: Terminology, Binary Trees, Properties of Binary trees, Array and linked Representation
of Binary Trees, Binary Tree Traversals – In-order, post-order, pre-order; Threaded binary trees,
Binary Search Trees – Definition, Insertion, Deletion, Traversal, Searching. AVL Trees and Red
Black Trees construction, Selection Trees, Forest.

Text book 1:5.1-5.3, 5.7-5.9, 10.2, 10.3

4.1 Trees: Terminology

In linear data structure, data is organized in sequential order and in non-linear data structure,
data is organized in random order.
Tree is a non-linear data structure which organizes data in hierarchical fashion and the
tree structure follows a recursive pattern of organizing and storing data.

A tree is a non-linear data structure which contains a finite set of one or more nodes such
that: (1) There is a specially designated node called the root. (2) The remaining nodes are
partitioned into n ≥ 0 disjoint sets T1, …, Tn, where each of these sets is a tree. We call T1, …,
Tn as the subtrees of the root.
Every individual element is called as Node. Node in a tree data structure, stores the actual data
of that particular element and link to next element in hierarchical structure.

Example

1. Root
In a tree data structure, the first node is called as Root Node. Every tree must have root node.
We can say that root node is the origin of tree data structure. In any tree, there must be only
one root node. We never have multiple root nodes in a tree. Ex: ‘A’ in the above tree

2. Edge
In a tree data structure, the connecting link between any two nodes is called as EDGE.
In a tree with 'N'number of nodes there will be a maximum of 'N-1' number of edges.
Ex: Line between two nodes.

3. Parent
In a tree data structure, the node which is predecessor of any node is called as PARENT

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 1

Data Structures and Applications (CS204) Module 4

NODE. In simple words, the node which has branch from it to any other node is called as
parent node. Parent node can also bedefined as "The node which has child / children".

Ex: A,B,C,E & G are parent nodes

4. Child
In a tree data structure, the node which is descendant of any node is called as CHILD Node.
In simple words,the node which has a link from its parent node is called as child node. In a
tree, any parent node can have anynumber of child nodes. In a tree, all the nodes except root
are child nodes. Ex: B & C are children of A, G & H are children of C and K child of G

5. Siblings
In a tree data structure, nodes which belong to same Parent are called as SIBLINGS. In
simple words, the nodes with same parent are called as Sibling nodes. Ex: B & C are
siblings, D, E and F are siblings, G & H are siblings, I & J are siblings

6. Leaf
In a tree data structure, the node which does not have a child is called as LEAF Node. In simple
words, a leaf is a node with no child. In a tree data structure, the leaf nodes are also called as
External Nodes. External node is also a node with no child. In a tree, leaf node is also called
as 'Terminal' node. Ex: D,I,J,F,K AND H are leaf nodes

7. Internal Nodes
In a tree data structure, the node which has atleast one child is called as INTERNAL Node.
In simple words,an internal node is a node with atleast one child.
In a tree data structure, nodes other than leaf nodes are called as Internal Nodes. The root node
is also said to be Internal Node if the tree has more than one node. Internal nodes are also
called as 'Non-Terminal' nodes.
Ex: A,B,C,E & G

8. Degree of a node
In a tree data structure, the total number of children of a node is called as DEGREE of that
Node. In simple words, the Degree of a node is total number of children it has. The highest
degree of a node among all the nodes in a tree is called as 'Degree of Tree'. Ex: Degree of
B is 3, A is 2 and of F is 0. Degree of Tree is 3.

9. Level of a node
In a tree data structure, the root node is said to be at Level 0 and the children of root node are
at Level 1 and the children of the nodes which are at Level 1 will be at Level 2 and so on... In
simple words, in a tree each step from top to bottom is called as a Level and the Level count
starts with 0 and incremented by one at each level (Step).

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 2

Data Structures and Applications (CS204) Module 4

10. Height
In a tree data structure, the total number of edges from leaf node to a particular node in the
longest path is called as HEIGHT of that Node. In a tree, height of the root node is said
to be height of the tree. In a tree, height of all leaf nodes is 0.

11. Depth
In a tree data structure, the total number of edges from root node to a particular node is called
as DEPTH of that Node. In a tree, the total number of edges from root node to a leaf node in
the longest path is said to be Depth of the tree. In simple words, the highest depth of any leaf
node in a tree is said to be depth of that tree.In a tree, depth of the root node is 0.

12. Path
In a tree data structure, the sequence of Nodes and Edges from one node to another node is
called as PATH between the two Nodes. Length of a Path is total number of nodes in that path.
In below example the path A -B - E - J has length 4.

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 3

Data Structures and Applications (CS204) Module 4

13. Sub Tree

In a tree data structure, each child from a node forms a subtree recursively. Every child
node will form a subtree on its parent node.

The ancestors of a node are all the nodes along the path from the root to that node.
Ex: ancestor of j is B & A
A forest is a set of n>=0 disjoint trees. If we remove the root of a tree we get a forest. For
example, in figure 1 if we remove A we get a forest with two trees.
Types of Trees
1) General Tree
2) Binary Tree
3) Threaded Binary Tree
4) Binary Search Tree
5) AVL Tree
6) Red Black Tree
7) Selection Tree
General Tree Representations
A tree is called a general tree when there is no constraint imposed on the hierarchy of the tree.
In general tree, each node can have infinite number of children. This tree is the super set of all
other types of trees.
Representations of General Tree Structure:
1. List Representation
2. Left Child - Right Sibling Representation
3. Degree two Representation (Binary Tree Representation)

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 4

Data Structures and Applications (CS204) Module 4

Consider the following tree...

1. List Representation
There are several ways to draw a tree. One useful way is as a list. The tree in the above figure
could be written as the list (A(B(D,E(I,J),F),C(G(K),H)) – list representation (with rounded
brackets). The information in the root node comes first followed by a list of the subtrees
of that node. Now, how do we represent a tree in memory? If we wish to use linked lists, then
a node must have a varying number of fields depending upon the number of branches.
Possible node structure for a tree of degree k called k-ary tree
Data link1 link2 ....... link k

Each link field is used to point to a subtree. This node structure is cumbersome for the
following reasons (1) Multiple node structure for different tree nodes (2) Waste of space (3)
Excessive use of links.
The other alternate method is to have linked list of child nodes which allocates memory only
for the nodes which have children.
In this representation, we use two types of nodes, one for representing the node with data and
another for representing only references. We start with a node with data from root node in the
tree. Then it is linked to an internal node through a reference node and is linked to any other
node directly. This process repeats for all the nodes in the tree.

ref link Reference Node data link Data Node

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 5

Data Structures and Applications (CS204) Module 4

2. Left Child - Right Sibling Representation

In this representation, we use list with one type of node which consists of three fields namely
Data field, Left child reference field and Right sibling reference field. Data field stores the
actual value of a node, left reference field stores the address of the left child and right reference
field stores the address of the right sibling node. Graphical representation of that node is as
follows...

In this representation, every node's data field stores the actual value of that node. If that node
has left child, then left reference field stores the address of that left child node otherwise that
field stores NULL. If that node has right sibling then right reference field stores the address
of right sibling node otherwise that field stores NULL.

3. Degree two tree (Binary Tree)

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 6

Data Structures and Applications (CS204) Module 4

The left child-right sibling representation can be converted to a degree two tree by simply
rotating the right sibling pointers clockwise by 45 degrees. In this representation, the two
children of a node are called the left child and the right child. It is equivalent to converting a
normal tree to binary tree. Degree two trees or left child-right child trees are nothing but
binary trees.
1. Root of the general tree is the root of the binary tree.
2. The first child node of any node in the general tree remains as the left subtree’s root in
the binary tree.
3. Its right sibling in general tree becomes the right child node.

4.2 Binary Tree (Degree two tree)

In a general tree, every node can have arbitrary number of children. Binary tree is a special
type of tree data structure in which every node can have a maximum of 2 children. One is
known as left child and the other is known as right child. A tree in which every node can
have a maximum of two children is called as Binary Tree. In a binary tree, every node can
have either 0 children or 1 child or 2 children but not more than 2 children. Example

Types of Binary Trees

1. Full/Strictly Binary Tree
In a binary tree, every node can have a maximum of two children. But in strictly binary tree,
every node should have exactly two children or none. That means every internal node must
have exactly two children. A strictly Binary Tree can be defined as follows...
A binary tree in which every node has either two or zero number of children is called Strictly
Binary Tree. Strictly binary tree is also called as Full Binary Tree or Proper Binary
Tree or 2-Tree.

Strictly binary tree data structure is used to represent mathematical expressions.

A Binary Expression Tree is - A special kind of binary tree in which:
1. Each leaf node contains a single operand

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 7

Data Structures and Applications (CS204) Module 4

2. Each non-leaf node contains a single binary operator

3. The left and right subtrees of an operator node represent sub expressions that must be
evaluated before applying the operator at the root of the subtree.
Example :

2. Complete Binary Tree

In a binary tree, every node can have a maximum of two children. But in strictly binary tree,
every node should have exactly two children or none and in complete binary tree all the nodes
must have exactly two children and at every level of complete binary tree there must be 2 level
number of nodes. For example at level 2 there must be 22 = 4 nodes and at level 3 there must

be 23 = 8 nodes.

A binary tree in which every internal node has exactly two children and all leaf nodes are
at same level is called Complete Binary Tree. Complete binary tree is also called as Perfect
Binary Tree.

3. Almost complete Binary Tree

It is complete binary tree but completeness property is not followed in last level. In the above
tree absence of leaf nodes L, M, N, O and P indicates its almost complete binary tree.

4. Right Skewed BT
Here the tree grows only towards right. The height of the right sub tree is greater than the
left sub tree.

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 8

Data Structures and Applications (CS204) Module 4

5. Left Skewed BT
Here the tree grows only towards left. The height of the left subtree is greater than the right sub
tree.

6.Extended Binary Tree

A binary tree can be converted into Full Binary tree by adding dummy nodes to existing
nodes wherever required. The full binary tree obtained by adding dummy nodes to a binary
tree is called as Extended BinaryTree.
In above figure, a normal binary tree is converted into full binary tree by adding dummy nodes
(In pink colour).

7. Binary Search Tree (BST)

BST is a binary tree with a difference that for any node x, data of left subtree <= data(x)
and data of rightsubtree > data(x). The above condition should be satisfied by all the nodes.

4.3 Binary Tree Representations

A binary tree data structure is represented using two methods. Those methods are as follows...
1. Array Representation
2. Linked List Representation
Consider the following binary tree...

1. Array Representation (static)

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 9

Data Structures and Applications (CS204) Module 4

In array representation of binary tree, we use a one dimensional array (1-D Array) to represent
a binary tree. Consider the above example of binary tree and it is represented as follows...

To represent a binary tree of depth 'n' using array representation, we need one dimensional
array with a maximum size of 2n+1 - 1.
For any node with the position i (index of parent node is i), 2i + 1 gives the position of the left
child & 2i + 2 gives the positon of the right child. For any node with a position i, its parent
node position is identified by using formula (i-1) / 2.
If i is the position of the left child i+1 gives the position of right child.

Advantages of array representation

 Faster access
 Easy for implementation
 Good for complete binary trees

Disadvantages

 Wastes memory for skewed trees

 Implementation of operations requires rearranging(shifting)of array elements

2. Linked List Representation (dynamic)

The linked notation uses a doubly linked list to represent a binary tree. In a double linked list,
every node consists of three fields. First field for storing left child address, second for storing
actual data and third for storing right child address.In this linked list representation, a node has
the following structure...

The above example of binary tree represented using Linked list representation is shown as
follows...

4.4 Binary Tree Traversals

Tree traversal is a method of visiting the nodes of a tree in a particular order. The tree

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 10

Data Structures and Applications (CS204) Module 4

nodes are visited exactly once and displayed as they are visited.

Displaying (or) visiting order of nodes in a binary tree is called as Binary Tree Traversal.
There are five types of binary tree traversals.
1. In - Order Traversal
2. Pre - Order Traversal
3. Post - Order Traversal
4. Iterative In-Order Traversal
5. Level Order Traversal
Consider the following binary tree...

1. In - Order Traversal ( left child - root – right child )

In In-Order traversal, the root node is visited between left child and right child. In this traversal,
the left childnode is visited first, then the root node is visited and later we go for visiting right
child node. This in-order traversal is applicable for every root node of all subtrees in the tree.
This is performed recursively for all nodes in the tree.

In-Order Traversal for above example of binary tree is : I - D - J - B - F - A - G - K - C – H

void inorder(struct node *root)
{
if(root!=NULL) struct node
{ {
inorder(root->left); int data;
printf("%d ",root->data); struct node *left, *right;
inorder(root->right); };
}
}

2. Pre - Order Traversal ( root – left child – right child )

In Pre-Order traversal, the root node is visited before left child and right child nodes. In this
traversal, the root node is visited first, then its left child and later its right child. This pre-order
traversal is applicable for every root node of all subtrees in the tree.

Pre-Order Traversal for above example binary tree is : A - B - D - I - J - F - C - G - K – H

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 11

Data Structures and Applications (CS204) Module 4

void preorder(struct node *root)

{
if(root!=NULL)
{
printf("%d ",root->data);
preorder(root->left);
preorder(root->right);
}
}

3. Post - Order Traversal ( left child – right child - root)

In Post-Order traversal, the root node is visited after left child and right child. In this traversal,
left child nodeis visited first, then its right child and then its root node. This is recursively
performed until the right most node is visited.

Post-Order Traversal for above example binary tree is : I - J - D - F - B - K - G - H - C – A

void postorder(struct node *root)
{
if(root!=NULL)
{
postorder(root->left);
postorder(root->right);
printf("%d ",root->data);
}
}
4. Iterative Inorder Traversal
Traversal techniques using recursion consumes system stack space. The stack space used may
not be acceptable for unbalanced trees of trees of larger heights. In such cases, iterative
traversal can be implemented by simulating stack space with the help of an array. Another
solution would be to use threaded binary trees during traversal.
#define size 10
int top=-1; Input:
struct Tree 1
{
int data; / \
struct Tree *lptr, *rptr; 2 3
};
typedef struct Tree node; / \
node *root,*stack[size]; 4 5
void push(node *temp) //function to push
{ Output: 4 2 5 1 3
if(top == size – 1) Explanation: Inorder traversal (Left->Root->Right)
{
printf(“stack full”); of the tree is 4 2 5 1 3.

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 12

Data Structures and Applications (CS204) Module 4

return;
}
stack[++top] = temp;
}
node *pop() //function to pop
{
if(top == – 1)
{
printf(“stack empty”);
return;
}
return(stack[top--]);
}
void iterative_inorder(node *root)
{
node *cur = root;
while(1)
{
while(cur!=NULL)
{
push(cur);
cur=cur->lptr;
}
if(top == -1)
break;
cur = pop();
printf(“%d “, cur->data);
cur=cur->rptr;
}
}
5. Level Order Traversal

 Level order traversal is a method of traversing the nodes of a tree level by level as in
breadth first traversal.

 Level order traversal uses queue thus avoiding stack space usage.

 Here the nodes are numbered starting with the root on level zero continuing with
nodes on level1, 2, 3…..

 The nodes at any level is numbered from left to right

 Visiting the nodes using the ordering of levels is called level order traversal

 Queue uses FIFO principle

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 13

Data Structures and Applications (CS204) Module 4

(ref :Wikipedia)
The level order traversal of the above tree is F B G A D I C E H
Implementation of level order traversal
void Level_Order(node *root)
{
int f = 0, r = -1;
node *q[size], *cur;
q[++r] = root;
while( r >= f)
{
cur = q[f++];
printf(“%d “, cur->data);
if(cur->lptr != NULL)
q[++r] = cur->lptr;
if(cur->rptr != NULL)
q[++r] = cur->rptr;
}
}
Building Binary Tree from Traversal Pairs:
Sometimes it is required to construct a binary tree if its traversals are known. From a single
traversal it is not possible to construct unique binary tree. However any of the two traversals
are given then the corresponding tree can be drawn uniquely:
• Inorder and preorder
• Inorder and postorder
• Inorder and level order
The basic principle for formulation is as follows:
If the preorder traversal is given, then the first node is the root node. If the postorder traversal
is given then the last node is the root node. Once the root node is identified, all the nodes in
the left sub-trees and right sub-trees of the root node can be identified using inorder.
Same technique can be applied repeatedly to form sub-trees.
It can be noted that, two traversals are essential out of which one should be inorder traversal
and another preorder or postorder; alternatively, given preorder and postorder traversals,
binary tree cannot be obtained uniquely.
Reconstructing binary tree from Inorder and Preorder traversal
Consider the following traversals of the tree.
Inorder = {4, 2, 5, 1, 6, 3, 7} Preorder = {1, 2, 4, 5, 3, 6, 7}
Steps of construction:

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 14

Data Structures and Applications (CS204) Module 4

First element in Preorder will be the root of the tree, here its 1. Now search the element 1 in
inorder[], say we find it at position i, once we find it, make note of elements which are left to i
(this will construct the left subtree) and elements which are right to i ( this will construct the
right subtree). Same technique can be applied repeatedly to form sub-trees.

Example 2:
Construct a binary tree from a given preorder and inorder sequence:
Preorder: A B D G C E H I F
Inorder: D G B A H E I C F
Solution:
Making the nodes according to the preorder sequence and the child nodes according to the
inorder sequence,

4.5 Properties of Binary Tree

1. The Maximum number of nodes on level i of a Binary tree is 2i-1, i>=1 (Consider root as
level 1)

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 15

Data Structures and Applications (CS204) Module 4

The Proof by induction on i:

Induction base: Root is the only node on level i = 1.
Hence max no of nodes on level i =1, 2i-1= 20=1

Induction Hypothesis:
Let i be an arbitrary positive integer > 1
Assume that max no of nodes on level i-1 is 2i-1-1=2i-2
Induction Step:
We know that max no of nodes on level i-1 is 2 i-2 by induction hypothesis
We know that each node in a Binary Tree has maximum degree 2.
Max no of nodes on level i = twice the max no of nodes on level i-1 i.e 2*2 i-2

= 2i-2+1 =2i-1. Hence the proof.

2. Prove that maximum number of nodes in a Binary Tree of depth k is 2k – 1, k>=1
Total no of nodes = 20 + 21 + 22 + .............. + 2i
The above sequence is in geometric progression
= (2 i+1 - 1) / (2 – 1)
= 2 i+1 - 1
= 2k – 1 (where i+1 = k = depth of tree)
=> max no of nodes in a BT of depth K = 2k - 1

3. [Relation between no of leaf nodes and degree-2 nodes] For any nonempty Binary Tree
T, if N0 is the no of leaf nodes and N2 no of nodes of degree 2 then N0 = N2 +1
Proof: Let N1 be the no of nodes of degree 1 and N be the total no of nodes

Since all nodes in T are atmost of degree 2 we have

N = N0 + N1 + N2 (1)

If we count no of branches in a Binary Tree we see that every node except the root has
a branch leading into it. If B is the no of branches then
N=B+1
All branches stem from a node of degree one or two.
Therefore B = N1 + 2N2

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 16

Data Structures and Applications (CS204) Module 4

 N=B+1
 N = N1 + 2N2 + 1 (2)

 from (1) and (2), we get

N0 + N1 + N2 = N1 + 2N2 + 1

N0 = N2 + 1
Hence the proof.

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 17

Data Structures and Applications (CS204) Module 4

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 18

Data Structures and Applications (CS204) Module 4

References:

http://btechsmartclass.com/D

S/U3_T3.html

http://www.iare.ac.in/sites/default/files/DS.pdf

Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 19