Module 4: Tree (21CS32) 1
Module 4
Tree
Trees: Introduction, Binary Trees, Binary Tree Traversals, Threaded Binary Trees., Binary Search trees,
Selection Trees, Forests.
INTRODUCTION TO TREES
Till now, we focused only on linear data structures such as stacks, queues and linked lists. But, in
real-world situations, data relationships are not always linear. Tree is one such non-linear data
structure which stores the data elements in a hierarchical manner. Each node of the tree stores a
data value, and is linked to other nodes in a hierarchical fashion. In this chapter, we will learn about
the different types of trees and their related operations. Most importantly, we will focus on binary
tree and its variants, which are widely used in the field of computer science.
4.1 BASIC CONCEPT
A tree is defined as a finite set of elements or nodes, such that
i) 1. One of the nodes present at the top of the
tree is marked as root node.
ii) 2. The remaining elements are partitioned
across multiple subtrees present below the root
node. Figure 4.1 shows a sample tree T.
Figure 4.1 : Tree T
Here, T is a simple tree containing ten nodes with A being the root node. The node A contains
two subtrees. The left subtree starts at node B while the right subtree starts at node C. Both the
subtrees further contain subtrees below them, thus indicating recursive nature of the tree data
structure. Each node in the tree has zero or more child nodes.
4.2 Tree Terminology
There are a number of key terms associated with trees. Table 6.1 lists some of the important key
terms.
Table 4.1 Tree terminology
Key Term Description Example (Refer to Fig. 4.1)
Node It is the data element of a tree. Apart from storing a A, B, C, D
value, it also specifies links to the other nodes.
Root It is the top node in a tree. A
Parent A node that has one or more child nodes present B is the parent node of D and E
below it is referred as parent node.
By: Dr. Rama Satish KV, RNSIT, Bengaluru. For latest updates visit: [Link]
Module 4: Tree (21CS32) 2
Child All nodes in a tree except the root node are child H, I and J are child nodes of E
nodes of their immediate predecessor nodes.
Leaf It is the terminal node that does not have any child G, H, I, J and F are leaf nodes
nodes.
Internal All nodes except root and leaf nodes are referred as B, C, D and E are internal nodes
node internal nodes.
Sibling All the child nodes of a parent node are referred as D and E are siblings
siblings.
Degree The degree of a node is the number of subtrees Degree of A is 2
coming out of the node. Degree of E is 3
Level All the tree nodes are present at different levels. A is at level 0
Root node is at level 0, its child nodes are at level 1, B and C are at level 1
and so on. G, H, I, J are at level 3
Height It is the maximum level of a node in the tree. Depth of tree T is 3
Path It is the sequence of nodes from source node till A–B–E–J
destination node.
4.3 BINARY TREE
Binary tree is one of the most widely used non-linear
data structures in the field of computer science. It is a
restricted form of a general tree. The restriction that it
applies to a general tree is that its nodes can have a
maximum degree of 2. That means, the nodes of a binary
tree can have zero, one or two child nodes but not more
than that. Figure 4.2 shows a binary tree. Figure 4.2 : Binary Tree
4.4 BINARY TREE REPRESENTATION
The sequential representation of binary trees is done by using arrays while the linked representation
is done by using linked lists.
4.4.1 Array Representation
In the array representation of binary trees, one-dimensional array is used for storing the node
elements. The following rules are applied while storing the node elements in the array:
a. The root node is stored at the first position in the array while its left and right child nodes
are stored at the successive positions.
b. If a node is stored at index location i then its left child node will be stored at location 2i+1
while the right child node will be stored at location 2i+2. Let us consider a binary tree T1,
as shown in Fig. 4.3.
By: Dr. Rama Satish KV, RNSIT, Bengaluru. For latest updates visit: [Link]
Module 4: Tree (21CS32) 3
Figure 4.3 : Array representation of Tree
Here, T1 is a binary tree containing seven nodes with A being the root node. B and C are the left
and right child nodes of A respectively. Let us apply the rules explained earlier to arrive at the
array representation of binary tree T1. Figure 4.3 shows the array representation.
4.4.2 Linked Representation
To avoid the disadvantages associated with array representation, linked representation is used for
implementing binary trees. It uses a linked list for storing the node elements. Each tree node is
represented with the help of the linked list node comprising of the following fields:
a. INFO Stores the value of the tree node.
b. LEFT Stores a pointer to the left child.
c. RIGHT Stores a pointer to the right child.
In addition, there is a special pointer that points at the root node. Figure 4.4 shows how linked list
is used for representing a binary tree in memory.
Figure 4.4 : Linked List representation of Tree
The linked representation of binary tree uses dynamic memory allocation technique for adding new
nodes to the tree. It reserves only that much amount of memory space as is required for storing its
node values. Thus, linked representation is more efficient as compared to array representation.
By: Dr. Rama Satish KV, RNSIT, Bengaluru. For latest updates visit: [Link]
Module 4: Tree (21CS32) 4
Shortcoming of array representation: Insertion and deletion of nodes from middle of a tree requires
movement of potentially many nodes to reflect the change in level number of these nodes. These
problems can be overcome easily through the use of a linked representation.
Each node has three fields:
1) Left Child,
2) Data and
3) Right Child
It is defined in C as shown
below:
typedef struct node *treePointer;
typedef struct
{
int data;
treePointer leftChild, rightChild;
} node;
Root of tree is stored in the data member 'root' of Tree. This data member serves as access-pointer
to the tree.
4.5 BINARY TREE TRAVERSAL
Traversal is the process of visiting the various elements of a data structure. Binary tree traversal
can be performed using three methods:
a. Preorder
b. Inorder
c. Postorder
a. Preorder: The preorder traversal method performs the following operations:
(a) Process the root node (N).
(b) Traverse the left subtree of N (L).
(c) Traverse the right subtree of N (R).
By: Dr. Rama Satish KV, RNSIT, Bengaluru. For latest updates visit: [Link]
Module 4: Tree (21CS32) 5
b. Inorder: The inorder traversal method performs the following operations:
(a) Traverse the left subtree of N (L).
(b) Process the root node (N).
(c) Traverse the right subtree of N (R).
c. Postorder: The postorder traversal method performs the following operations:
(a) Traverse the left subtree of N (L).
(b) Traverse the right subtree of N (R).
(c) Process the root node (N).
Consider the following binary tree:
By: Dr. Rama Satish KV, RNSIT, Bengaluru. For latest updates visit: [Link]
Module 4: Tree (21CS32) 6
Figure 4.5 : Binary tree traversal
Example - For the above binary tree, deduce the following:
(a) Preorder traversal sequence
(b) Inorder traversal sequence
(c) Postorder traversal sequence
Solution : (a) Preorder traversal sequence
A–B–D–E–G–C–F
(b) Inorder traversal sequence
D–B–G–E–A–C–F
(c) Postorder traversal sequence
D–G–E–B–F–C–A
4.5.1 Inorder Tree Traversal without Recursion (Iterative Inorder Tree Traversal)
Using Stack is the obvious way to traverse tree without recursion. Below is an algorithm for
traversing binary tree using stack.
1) Create an empty stack S.
2) Initialize current node as root
3) Push the current node to S and set current = current->left until current is NULL
4) If current is NULL and stack is not empty then
a) Pop the top item from stack.
b) Print the popped item, set current = popped_item->right
c) Go to step 3.
5) If current is NULL and stack is empty then we are done.
By: Dr. Rama Satish KV, RNSIT, Bengaluru. For latest updates visit: [Link]
Module 4: Tree (21CS32) 7
4.6 Threaded Binary Trees
• In the linked representation of binary trees, more than one half of the link fields contain
NULL values which results in wastage of storage space.
• If a binary tree consists of n nodes then n+1 link fields contain NULL values. So in order
to effectively manage the space, a method was devised by Perlis and Thornton in which
the NULL links are replaced with special links known as threads.
• Such binary trees with threads are known as threaded binary trees. Each node in a
threaded binary tree either contains a link to its child node or thread to other nodes in the
tree.
The idea of threaded binary trees is to make inorder traversal
faster and do it without stack and without recursion. A
binary tree is made threaded by making all right child pointers
that would normally be NULL point to the inorder successor
of the node (if it exists).
4.6.1 Types of Threaded Binary Tree
• One-way threaded Binary Tree ( Single)
• Two-way threaded Binary Tree (Double)
By: Dr. Rama Satish KV, RNSIT, Bengaluru. For latest updates visit: [Link]
Module 4: Tree (21CS32) 8
4.6.2 Construction of Threaded Binary Tree
First step is to find the Inorder
traversal of the given binary tree. This
tree has 9 nodes and 10 NULL links,
which have been replaced by threads.
if we traverse the tree in inorder, the
nodes will be visited in the order
H,D,I,B,E,A,F,C,G. for example, node E has a predecessor thread that points to B and a successor
thread that points to A.
4.6.3 Threaded Binary Tree Implementation
struct Node
{
int data;
struct Node *left, *right;
bool rightThread;
}
Since right pointer is used for two purposes, the boolean variable rightThread is used to indicate
whether right pointer points to right child or inorder successor.
4.6.4 Inorder traversal in Threaded binary tree
// C code to do inorder traversal in a threaded binary tree
void inOrder(struct Node* root)
{
struct Node* cur = leftMost(root);
while (cur != NULL)
{
printf("%d ", cur->data);
// If this node is a thread node,
then go to inorder successor
if (cur->rightThread == 1)
cur = cur->right;
else // Else go to the leftmost child in right subtree
cur = leftmost(cur->right);
}
}
// Utility function to find leftmost node in a tree rooted with n
struct Node* leftMost(struct Node* n)
{
if (n == NULL)
return NULL;
while (n->left != NULL)
n = n->left;
return n;
}
By: Dr. Rama Satish KV, RNSIT, Bengaluru. For latest updates visit: [Link]
Module 4: Tree (21CS32) 9
4.6.5 Advantages and Disadvantages of Threaded Binary Tree
Advantages of Threaded Binary Tree
• In threaded binary tree, linear and fast traversal of nodes in the tree so there is no
requirement of stack. If the stack is used then it consumes a lot of memory and time.
• It is more general as one can efficiently determine the successor and predecessor of any
node by simply following the thread and links. It almost behaves like a circular linked list.
Disadvantages of Threaded Binary Tree
• When implemented, the threaded binary tree needs to maintain the extra information for
each node to indicate whether the link field of each node points to an ordinary node or the
node's successor and predecessor.
• Insertion into and deletion from a threaded binary tree are more time consuming since both
threads and ordinary links need to be maintained.
4.7 Binary Search Tree (BST)
A binary tree is referred as a binary search tree if for any node n in the tree:
1) Each node has exactly one key and the keys in the tree are distinct.
2) The keys in the left subtree are smaller than the key in the root.
3) The keys in the right subtree are larger than the key in the root.
4) The left and right subtrees are also binary search trees.
Duplicates in binary search tree are not allowed.
4.7.1 Declaring BST
struct BST
{
int item;
struct BST *llink, *rlink;
};
typedef struct BST* NODE;
In the above code a BST node is declared that has room for storing an integer data, leftlink and
right link pointers to left and right subtrees.
4.7.2 Operations on BST
The various operations performed on a binary search tree are:
1. Insert 2. Search 3. Delete
Whenever an element is to be inserted, first locate its proper location. Start searching from the root
node, then if the data is less than the key value, search for the empty location in the left subtree
and insert the data. Otherwise, search for the empty location in the right subtree and insert the data.
By: Dr. Rama Satish KV, RNSIT, Bengaluru. For latest updates visit: [Link]
Module 4: Tree (21CS32) 10
4.8.1 Insert operation
Firstly verify, if the tree already contains the node with the same data. If the search is successful,
then the new node(duplicate element) cannot be inserted into the binary search tree. If the search
is unsuccessful, then we can insert the new node at that point where the search terminated.
Example:
Program code to implement insert operation.
/* This function is for creating a binary search tree */
NODE insert(NODE root)
{
NODE temp, cur, prev;
int item;
printf("\nEnter The Element "); scanf("%d", &item);
temp = (NODE) malloc(sizeof(struct BST));
temp->llink = NULL;
temp->rlink = NULL;
temp->item = item;
if (root == NULL)
return temp;
prev = NULL;
cur = root;
while(cur != NULL) {
prev = cur;
if (item < cur-> item)
cur = cur->llink;
else
cur = cur->rlink;
}
if (item < prev->item)
prev->llink = temp;
else
prev->rlink = temp;
return root;
}
By: Dr. Rama Satish KV, RNSIT, Bengaluru. For latest updates visit: [Link]
Module 4: Tree (21CS32) 11
4.8.2 Binary Search Tree Traversal
Traversal is the process of visiting the various elements of a data structure. Binary tree traversal
can be performed using three methods: 1. Preorder 2. Inorder 3. Postorder
The preorder traversal method performs the following operations:
(a) Process the root node (N).
Traversal Order
(b) Traverse the left subtree of N (L). 100 – 20 – 10 – 30 – 200 – 150 - 300
(c) Traverse the right subtree of N (R)
The inorder traversal method performs the following operations:
(a) Traverse the left subtree of N (L).
(b) Process the root node (N).
(c) Traverse the right subtree of N (R).
10 – 20 – 30 – 100 – 150 – 200 - 300
The Postorder traversal method performs the following operations:
(a) Traverse the left subtree of N (L).
(b) Traverse the right subtree of N (R).
(c) Process the root node (N).
10 – 30 – 20 – 150 – 300 – 200 - 100
By: Dr. Rama Satish KV, RNSIT, Bengaluru. For latest updates visit: [Link]
Module 4: Tree (21CS32) 12
4.8.3 Binary Search Tree : Searching
The search operation involves traversing the various nodes of the
binary tree to search the desired element. The sorted nature of the tree
greatly benefits the search operation as with each iteration, the number
of nodes to be searched gets reduced.
For example, if the value to be searched is less than the root value then
the remainder of the search operation will only be performed in the left
subtree while the right subtree will be completely ignored.
4.8.4 Binary Tree Construction from Traversals
Solution:
Solution :
By: Dr. Rama Satish KV, RNSIT, Bengaluru. For latest updates visit: [Link]
Module 4: Tree (21CS32) 13
4.8.5 Deletion from a binary search tree
Deletion of a leaf: To delete 35 from the tree of figure, the left-child field of its parent is set to NULL.
➔
Deletion of a non-leaf that has only one child: The node containing the dictionary pair to be
deleted is freed, and its single-child takes the place of the freed node. So, to delete the 5 from the
tree in figure, we simply change the pointer from the parent node to the singlechild node.
➔
Deletion of a non-leaf that has only two child nodes:
The pair to be deleted is replaced by the smallest one in its right subtree. For instance, if we wish
to delete the pair with key 30 from the tree in following figure then we replace it by key 35 as
shown in figure
4.9 Application of Trees: EXPRESSION TREES
The expression tree is a binary tree in which each internal node corresponds to the
operator and each leaf node corresponds to the operand so for example expression
tree for 3 + ((5+9)*2) would be:
Following figures shows the example of Expression tree:
By: Dr. Rama Satish KV, RNSIT, Bengaluru. For latest updates visit: [Link]
Module 4: Tree (21CS32) 14
Figure 4.10 : Examples of Expression Tree
Once an expression tree is constructed, we can traverse it in three ways:
• Inorder Traversal
• Preorder Traversal
• Postorder Traversal
Figure 4.1 shows some more expression trees that represent arithmetic expressions given in infix
form.
4.9.1 Construction of Expression Tree
An expression tree can be generated for the infix and postfix expressions. An algorithm to
convert a postfix expression into an expression tree is as follows:
• Read the expression from left to right and one symbol at a time.
• If the symbol is an operand, we create a one-node tree and push a pointer to it onto a
stack.
• If the symbol is an operator, we pop pointers to two trees T1 and T2 from the stack (T1
is popped first) and form a new tree whose root is the operator and whose left and right
children point to T2 and T1 respectively. A pointer to this new tree is then pushed onto
the stack.
By: Dr. Rama Satish KV, RNSIT, Bengaluru. For latest updates visit: [Link]
Module 4: Tree (21CS32) 15
By: Dr. Rama Satish KV, RNSIT, Bengaluru. For latest updates visit: [Link]
Module 4: Tree (21CS32) 16
4.9.2 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.
By: Dr. Rama Satish KV, RNSIT, Bengaluru. For latest updates visit: [Link]
Module 4: Tree (21CS32) 17
By: Dr. Rama Satish KV, RNSIT, Bengaluru. For latest updates visit: [Link]
Module 4: Tree (21CS32) 18
By: Dr. Rama Satish KV, RNSIT, Bengaluru. For latest updates visit: [Link]
Module 4: Tree (21CS32) 19
By: Dr. Rama Satish KV, RNSIT, Bengaluru. For latest updates visit: [Link]
Module 4: Tree (21CS32) 20
4.10 Selection tree
The Tournament tree is a complete binary tree with n external nodes and n – 1 internal nodes.
The external nodes represent the players, and the internal nodes are representing the winner of
the match between the two players. This tree is also known as Selection tree.
There are some properties of Tournament trees. These are like below −
• This tree is rooted. So the link in the tree and directed path from parent to children, and
there is a unique element with no parents
• The parent value is less or equal to that node to general any comparison operators, can
be used as long as the relative value of the parent and children are invariant throughout
the tree
• Trees with a number of nodes not a power of 2, contain holes. Holes can be present at any
place in the tree.
• This tree is a proper generalization of binary heaps
• The root will represent overall winner of the tournament.
By: Dr. Rama Satish KV, RNSIT, Bengaluru. For latest updates visit: [Link]
Module 4: Tree (21CS32) 21
There are two types of Tournament Trees −
• Winner Tree
• Looser Tree
4.10.1 Winner Tree
Winner tree is a complete binary tree, in which each node is representing the
smaller or greater of its two children, is called winner tree. The root is holding the
smallest or greatest node of the tree. The winner of the tournament tree is the
smallest or greatest n key in all the sequences. It is easy to see that winner tree
can be formed in O(log n) time.
Example − Suppose there are some keys, 3, 5, 6, 7, 20, 8, 2, 9
4.10.2 Looser Tree
Looser Trees are complete binary tree for n players where n external nodes and
n – 1 internal nodes are present. The looser of the match is stored in the internal
nodes. But in this overall winner is stored at tree[0]. The looser is an alternative
representation, that stores the looser of a match at the corresponding node. An
advantage of the looser is that, to restructure the tree after winner tree been
output, it is sufficient to examine node on the path from leaf to root rather than
the sibling of the nodes on this path.
By: Dr. Rama Satish KV, RNSIT, Bengaluru. For latest updates visit: [Link]
Module 4: Tree (21CS32) 22
Example − To form a looser tree, we have to create winner tree at first.
Suppose there are some keys, 10, 2, 7, 6, 5, 9, 12, 1. So we will create minimum
winner tree at first.
Now, we will store looser of the match in each internal node.
4.11 Forest
A forest is an undirected graph in which any two vertices are
connected by at most one path. Equivalently, a forest is an
undirected acyclic graph, all of whose connected components are
trees; in other words, the graph consists of a disjoint union of
trees.
By: Dr. Rama Satish KV, RNSIT, Bengaluru. For latest updates visit: [Link]