Data Structures using „C‟ - Trees

Data Structures using „C‟ Unit 6

Unit 6 Trees
Structure:
6.1 Introduction
6.2 Overview of Tree Concept
Self assessment Questions
6.3 Binary tree
6.3.1 Strictly binary tree
6.3.2 Complete binary tree
6.3.3 Almost complete binary tree
6.3.4 Storage representation of a binary tree
Self assessment Questions
6.4 Various operations on binary trees using linked representation
6.4.1 Insertion Operation
6.4.2 Traversals
Self assessment Questions
6.5 Binary search tree (BST)
6.5.1 Insertion Operation
6.5.2 Searching
6.5.3 Other operations
6.5.3.1 To find maximum value in a tree BST
6.5.3.2 To find minimum value in a BST
6.5.3.3 Height of tree
6.5.3.4 Count nodes in a tree
6.5.3.5 Count leaves in a tree
6.5.3.6 Delete a node from the tree
Self assessment Questions
6.6 Summary
6.7 Terminal Questions
Data Structures using „C‟ Unit 6
Sikkim Manipal University Page No.: 171
6.1 Introduction
So far we have discussed the data structures where linear ordering was maintained using arrays and linked lists. These data structures and their relationships are invariably expressed using single dimension. For some problems it is not possible to maintain this linear ordering using linked lists. Using non-linear data structures such as trees, graphs, multi-linked structures etc., more complex relations can be expressed. In this unit on trees, we begin with some definitions, the various operations that can be performed on trees along with various applications.
Objectives
At the end of this unit, you will be able to understand the:
 Overview of Tree Concepts
 Binary Tree and its type
 Various operations on binary trees
 Binary Search Tree [BST]
 Tree operation implementation using C
6.2 Overview of Tree Concepts
A tree consists of a finite set of elements, called nodes and a finite set of directed lines, called branches that connect the nodes. The number of branches associated with a node is the degree of the node. When the branch is directed to wards the node, it is an indegree branch; When the branch is directed away from the node it is an outdegree branch, the sum of outdegree and indegree branches equals to the degree of the node.
“A tree consists of a finite set of elements, called nodes, and a finite set of directed lines, called branches, that connects the nodes”.
If the tree is not empty, then the first node is called as root. The indegree of root by definition is zero. With the exception of the root, all the nodes in a
Data Structures using „C‟ Unit 6
Sikkim Manipal University Page No.: 172
tree must have an indegree exactly one. All nodes in the tree can have zero, one or more branches leaving them; that is they may have an outdegree of zero, one or more.
Subtree Internal NodesNodes that are not root and not leaf are called as internal nodes.
Consider a tree shown in figure:
Parent: A node is a parent if it has successor nodes; means outdegree
greater than zero. (Your parents)
Child: A node is a child node if indegree is one. (You)
Siblings: Two or more nodes with same parent are siblings.
(Your bro and sis)
An ancestor is any node in the path from the root to the node. A descendant is any node on the path below the parent node; that is all nodes in the paths from a given node to a leaf are descendants of the node.
A tree may be divided into subtrees. A subtree is any connected structure below the root.
B C
Internal node
You
Bro/ Sis
Cousins
Uncles
/Aunts
A
root
leaf
parent
child
Grand Parent
Data Structures using „C‟ Unit 6
Sikkim Manipal University Page No.: 173
Elements of Tree
Root
The unique node with no predecessor
(node that comes before it).
Leaf
A node with no successors (nodes after it).
- there will usually be many leaves in a tree.
Non Leaf
A node which has both a parent and at least one child.
Children
The successors of a node.
Parent
The unique predecessor of a node.
Siblings
Two nodes that have the same parent. In a binary tree the two
children are called the left and right. In the figure to the right,
D and E are siblings. In this example m=2 so the tree is a binary tree
B
D
E
Root
B
D
E
Left tree
Right tree
B
D
F
Leaf
Non Leaf
B
D
E
Parent
or Root
Child or Successor
Siblings
Data Structures using „C‟ Unit 6
Sikkim Manipal University Page No.: 174
Internal Nodes
Nodes that are not root and not leaf are called as internal nodes.
Graph :
A graph G = (V, E) where V is set of vertices and E is set of edges. In the
graph shown in fig. 6. 1. a,
V = {1,2,3,4}
E = {(1,2), (1,3), (2,3), (3,4), (4,2)}
where E is represented as a set of ordered pairs (x, y), if and only if there is
an edge from vertex x to y with x as the initial node and y as the terminal
node. A graph in which every edge is directed is called a directed graph or
digraph as shown in. fig. 6.1.a. A graph in which every edge is undirected is
called an undirected graph and is shown in fig. 6.1.b. A graph is said to be a
mixed graph, if some of the edges are undirected and some of the edges
are directed as shown in fig. .1.c.
If there is a maximum of one edge between a pair of nodes in the graph, the
graph is called simple graph. The graphs shown in fig. 6.1 are all simple
graphs. In the graph shown in fig. 6.1.d, since vertex 4 is not adjacent to any
other nodes, the vertex 4 is called an insolated node. The total number of
edges leaving a node is called an outdegree of that node and the number of
edges incident on a node is called indegree of that node. Sum of outdegree
and indegree is the total degree of a node. The outdegree of node 2 in fig.
6.1.a is 1 and indegree is 2. So, the total degree of node 2 is 3. In a graph if
one vertex, say u, is reachable from vertex v and v is reachable from u, then
Data Structures using „C‟ Unit 6
Sikkim Manipal University Page No.: 175
the path from v to v through u or u to u through v is called a circuit or a cycle.
There is a cycle
C = ( (2,3), (3,4) ,,(4,2) )
in the graph shown in fig. 6.1.a. A simple digraph having no cycle is called
an acyclic graph.
A directed tree is an acyclic digraph, which has only one node with
indegree 0, and all other nodes have indegree 1. A node with an indegree 0
is called the root node and all other nodes are reachable from the root node.
The nodes that are all reachable from a node u are all called descendents of
u. The nodes from which u is reachable starting from the root node are
called ancestors of node u. The nodes, which are all reachable from It using
only one edge, are called children of node It and node u is the father for all
those children. All the nodes that are all left descendents of a node u form
the left subtree of u and the right descendents form the right subtree of node
u. A node in a directed tree that has an outdegree of 0, is called a leaf node
or a terminal node Le., a node with an empty left child and an empty right
child is called a leaf node.
Figure 6.2 Binary trees
Data Structures using „C‟ Unit 6
Sikkim Manipal University Page No.: 176
In the directed tree shown in figure 6.2.a, the ancestors of node 35 are 80, 60 and 100. The descendents for the node 60 are 80, 35, 30 and 40. The root node is 100 and the terminal nodes are 70, 35, 30 and 40. Note that the indegree of 100 is zero and all other nodes have an indegree 1 and all the leaf nodes have outdegree 0. All non-leaves are called internal nodes and leaf or terminal nodes are called external nodes.
The level of any node u is given by the number of edges in the path from root node. So, the level of root node is zero. In fig. 6.2.a, the node 35 is at level 3 and the node 100 at level 0. The Height or depth of a tree is one more than the maximum level in the tree. So, the height of the tree shown in fig. 6.2.a is 4 and that of tree shown in fig. 6.2.b is 1 and the height of an .empty. binary tree is zero.
Self Assessment Questions
1. Discuss the various Graphs with neat diagram.
2. Define Directed tree.
6.3 Binary Tree
It is a directed tree in which outdegree of each node is less than or equal to two i.e., each node in the tree can have 0, or 2 children. An empty tree is also a binary tree. A binary tree can also be defined recursively as follows:
A binary tree is a finite set with the following properties:
1. The first subset contains only one element and it is called root of the tree. If root contains NULL it is called empty binary tree.
2. The second subset is a binary tree called left sub tree. The left sub tree can be empty.
3. The third subset is a binary tree called right sub tree. The right sub tree can be empty.
Data Structures using „C‟ Unit 6
Sikkim Manipal University Page No.: 177
The trees shown in fig. 6.2 are all binary trees.
 Binary tree operations
A binary tree is a tree in which no node can have more than two subtrees. In other words, a node can have zero, one, or two sub trees. In other words A tree in which every parent has one or two children (but not more than that) is called as binary tree.
The “root” component of binary tree is the forefother of all children. But it can have only up to two children one “right” child and “left” child. These children can become fathers and each can produce only two children. In fact a child can become a father, grandfather, great grandfather and son. Fig shows five binary trees all with three nodes.
L left R Right
We can have binary trees with any number of nodes.
L
Root
L
Root
L
R
Root
R
Root
L
R
Root
Data Structures using „C‟ Unit 6
Sikkim Manipal University Page No.: 178
“A child cannot have more than one father. If it is so then the tree is not a binary tree. A binary tree node cannot have more than two subtrees.”
6.3.1 Strictly binary tree
If the outdegree of every node in a tree is either 0 or 2, then the tree is said to be strictly binary tree i.e., each node can have maximum two children or empty left and empty right child. The trees shown in fig. 6.2.e and fig. 6.2.f are strictly binary trees.
Example :
A binary tree is said to be strictly binary if every non-leaf node has non-empty left and right subtrees. Fig shows a strictly binary tree.
A Strictly binary tree
 The binary tree in the above fig is not strictly binary because the non-leaf node E has no right sub-tree and the non-leaf node C has no left sub-tree.
6.3.2 Complete binary tree
A strictly binary tree in which the number of nodes at any level i is 2i-1, then the tree is said to be a complete binary tree. The tree shown in fig. 6.2.f is a strictly binary tree and at the same time it is a complete binary tree.
B
A
C
D
E
F
G
Data Structures using „C‟ Unit 6
Sikkim Manipal University Page No.: 179
Example:
A Complete Binary tree
In a complete binary tree, the total number of nodes at level 0 is 1 i.e., 2°
Number of nodes at level 1 is 2 i.e., 21
Number of nodes at level 2 is 4 i.e., 22
Number of nodes at level 3 is 8 i.e., 23
……………………………………
……………………………………
……………………………………
Number of nodes at the last level d is 2d.
It is clear from the figure that all the nodes in the final level d are leaf nodes and the total number of leaf nodes is 2d. In a complete binary tree, we can easily find the number of non-leaf nodes. Now, let us find the number of non-leaf nodes in a complete binary tree. Total number of nodes in the complete binary tree =
2° + 21 + 22 + ………….2d.
A
B
C
E
D
H
I
J
K
F
G
L
M
N
O
Data Structures using „C‟ Unit 6
Sikkim Manipal University Page No.: 180
Summation of this series is given by
S = a( rn- 1) 1( r- 1)
where a = 1, n = d+ 1 and r = 2
So, total number of nodes nt = 2d+1- 1
Nodes at level d are all leaf nodes. So, number of non-leaf nodes is given by 2d+1 - 1 –2d which is equal to 2d - 1.
6.3.3 Almost complete binary tree
A tree of depth d is an almost complete binary tree, if the tree is complete up to the level d-l i.e., the total number of nodes at the level d-l should be 2d-1. The total number of nodes at level d may be equal to 2d. If the total number 'of nodes at level d is less than 2d, then the number of nodes at level d-l should be 2d-1 and in level d the nodes should be present only from left to right. The trees shown in fig. 6.3.a to fig. 6.3.c are all almost complete binary trees and the; rest are not. The nodes in an almost complete binary can be numbered level by level from left to right as shown in fig. 6.3.c.
Data Structures using „C‟ Unit 6
Sikkim Manipal University Page No.: 181
Figure 6.3 Binary trees
6.3.4 Storage representation of a binary tree
The trees can be represented using sequential allocation technique (using
arrays) or by allocating the memory for a node dynamically (using linked
allocation technique). In a linked allocation technique a node in a tree has
three fields:
 info which contains the actual information
 llink which contains address of the left subtree
 rlink -contains address of the right subtree.
So, a node can be represented using structure as shown below:
Data Structures using „C‟ Unit 6
Sikkim Manipal University Page No.: 182
struct node
{
int info;
struct node *llink;
struct node *rlink;
};
typedef struct node* NODE;
A pointer variable root can be used to point to the root node always. If the
tree is empty, the pointer variable root points to NULL indicating the tree is
empty. The pointer variable root can be declared and initialized as
NODE root = NULL;
Memory can be allocated or de-allocated using the functions getnode() and
freenode( ) as we discussed in linked lists in unit 9. A tree can also be
represented using an array, which is called sequential representation (array
representation). Consider the trees shown in fig. 6.4.a and fig. 6. 4.b.
Data Structures using „C‟ Unit 6
Sikkim Manipal University Page No.: 183
The nodes are numbered sequentially from 0. The node with position 0 is considered as the root node. If an index i is 0, it gives the position of the root node. Given the position of any other node i, 2i+1 gives the position of the left child and 2i+2 gives the position of the right child. If i is the position of the left child, i+ 1 gives the position of the right child and if i is the position of the right child, i-1 gives the position of the left child. Given the position of any node i, the parent position is given by (i-1) /2. If i is odd, it points to the left child otherwise, it points to the right child. The different ways in which a tree can be represented using an array is shown below.
 In the first representation shown below, some of the locations may be used and some may not be used. For this, a flag field namely, used is used just to indicate whether a memory location is used to represent a node or not. If flag field used is 0, the corresponding memory location is not used and indicates the absence of node at that position. So, each node contains two fields:
 info where the information is stored
 used indicates the presence or the absence of a node
The structure declaration for this is:
#define MAX_SIZE 200
struct node
{
int info;
int used;
};
typedef struct node NODE;
An array A of type NODE can be used to store different items and the declaration for this is shown below:
NODE A [MAX_SIZE];
Data Structures using „C‟ Unit 6
Sikkim Manipal University Page No.: 184
 An alternate representation is that, instead of using a separate flag field used to check the presence of a node, one can initialize each location in the array to 0 indicating the node is not used. Non-zero value in the location indicates the presence of the node. In section 6.7, a program is shown to create the tree and traverse it in different orders using this approach.
In the next section let us concentrate on how the linked allocation technique is used to create and manipulate the tree data structure along with various applications.
Self Assessment Questions
1. Define Binary tree? Discuss its properties.
2. Define Strictly Binary Tree?
3. Explain the Complete Binary tree.
4. Explain tree storage representation using sequential technique with suitable example.
6.4 Various operations on binary trees using linked representation
Let us see and implement various operations that can be performed on binary trees. Various operations that can be performed are:
 Insertion – Insert a given item into a tree
 Traversal – Visiting the nodes of the tree one by one
 Search – Search for the specified item
 Copying – To obtain exact copy of the given tree
 Deletion – To delete a node from the tree
6.4.1 Insertion Operation
Suppose the node pointed to by temp has to be inserted whose information field contains the item „I‟ as shown in next figure 6.5.
Data Structures using „C‟ Unit 6
Sikkim Manipal University Page No.: 185
Let 'd' be an array, which contains only the directions where the node temp has to be inserted. If 'd' contains 'LRLR', from the root node first moves towards left(L), then right(R), then left(L) and finally move towards right(R). Finally if the pointer points to NULL, at that position, node temp can be inserted otherwise, node temp can not be inserted.
To achieve this, one has to start from the root node. Let us use two pointers prev and cur where prev always points to parent node and cur points to child node. Initially cur points to root node and prev points to NULL. To start with, one can write the following statements.
prev = NULL
cur = root
Now keep updating the node pointed to by cur towards left if the direction is ('L ') otherwise, update towards right. The pointer variable prev always points to the parent node and cur points to the child node. Once all directions are over, if cur points to NULL, insert the node temp towards left or right based on the last direction. Otherwise, display an error message. In the following algorithm, an index variable i is used to access the directions. The C function to insert a node is shown in below example
Data Structures using „C‟ Unit 6
Sikkim Manipal University Page No.: 186
Example : Function to insert an item into a tree
NODE insert(int item, NODE root)
{
NODE temp; /* Node to be inserted */
NODE cur /* Child node */
NODE prev; /* Parent node */
char direction[.10]; /* Directions where the node has to be inserted */
int i; /* Maximum depth where a node can be inserted */
temp = getnode(); /* Obtain a node from the availability list */
temp->info = item; /* Copy the necessary information */
temp->llink = temp->rlink = NULL;
if ( root = = NULL ) return temp; /* Node is inserted for the first time */
printf("Give the directions where you want to insert\n");
scanf("%s", direction);
toupper(direction); /* Convert the directions to upper case */
prev = NULL;
cur = root;
/* find the position to insert */
for ( i = 0; i< strlen(direction) && cur != NULL; i+ +)
{
prev= cur; /* Parent */
if ( direction[i] == 'L' ) /* If direction is (L) move towards left */.
cur = cur->llink;
else /* Otherwise move towards right */
cur = cur->rlink;
}
if ( cur != NULL  i!= strlen(direction))
{
printf("Insertion not possible\n");
freenode(temp);
return root;
Data Structures using „C‟ Unit 6
Sikkim Manipal University Page No.: 187
}
/* insert the node at the leaf level */
if ( direction[i-1 ] == 'L' ) /* Attach the node to the left of the parent * /
prev->llink = temp;
else
prev->rlink = temp; /* Attach the node to the right of the parent */
return root;
}
6.4.2 Traversals
Traversing is the most common operation that can be performed on trees. In
the traversal technique each node in the tree is processed or visited exactly
once systematically one after the other. The different traversal techniques
are Inorder, Preorder and Postorder. Each traversal technique can be
expressed recursively.
Data Structures using „C‟ Unit 6
Sikkim Manipal University Page No.: 188
Algorithm for tree traversals:
 The preorder traversal of a binary tree can be recursively defined as follows
1. Process the root Node [N]
2. Traverse the Left subtree in preorder[L]
3. Traverse the Right subtree in preorder [R]
 The postorder traversal of a binary tree can be recursively defined as follows:
1. Traverse the Left subtree in postorder[L]
2. Traverse the Right subtree in postorder [R]
3. Process the root Node [N]
Self Assessment Questions :
1. List the various operations that can be performed on Binary tree.
2. Write a C function to insert an item into a tree.
3. Explain the tree traversal technique with suitable example for each.
4. Write an algorithm for preorder traversal of binary tree.
6.5 Binary Search Tree (BST)
A binary search tree is a binary tree in which for each node say x in the tree, elements in the left- subtree are less than info (x) and elements in the right subtree are greater or equal to info(x). Every node in the tree should satisfy this condition, if left subtree or right subtree exists. Other common operations performed on binary search trees are
 Insertion -An item is inserted
 Searching -Search for a specific item in the tree
 Deletion -Deleting a node from a given tree.
Data Structures using „C‟ Unit 6
Sikkim Manipal University Page No.: 189
6.5.1 Insertion Operation
Creating a binary search tree is nothing but repeated insertion of an item
into the existing tree. So, we concentrate on how to insert an item into the
tree. In a BST (Binary Search Tree), items towards left subtree of a node
temp will be less than info(temp) and the items in the right subtree are
greater or equal to info(temp).
Consider the BST shown in fig. 6.8. Suppose the node pointed to by temp
(with item 140) has to be inserted. The item 140 is compared with root node
i.e., 100. Since it is greater, the right subtree of root node has to be
considered. Now compare 140 with 200 and since it is less, consider the left
subtree of the node 200. Now, compare 140 with 150. Since it is less,
consider the left subtree of node 150. Since, left subtree of node 150 empty,
the node containing the Item 140 has to be inserted towards left of a node
150. Thus, to find the appropriate place and insert an item, the search
should start from the root node. This is achieved by using two pointer
variables prev and cur. The pointer variable prev always points to parent of
cur node. Initially cur points to root node and prev points to NULL i.e.,
prev = NULL
cur = root
Data Structures using „C‟ Unit 6
Sikkim Manipal University Page No.: 190
Now, as long as the item is less than info (cur), keep updating the node pointed to by the pointer variable cur towards left. Otherwise, update towards right. The pointer variable prev always points to the parent node and cur points to the child node. Once cur points to NULL, insert the node temp towards left (prev) if item is less than info (prev), otherwise insert towards right. The code corresponding to this can be
prev = NULL;
cur = root;
/* find the position where to insert */
while ( cur != NULL )
{
prev = cur;
cur = ( item < cur->info ) ? cur->llink : cur->rlink;
}
if ( item < prev->info)
prev->llink = temp;
else
prev->rlink = temp;
The above steps can be executed provided the tree exists. If the tree is empty initially, then make the node pointed to by temp itself as root node. The complete C function to insert an item into a binary search tree is shown in below example
Example 6.8: Function to insert an item into an ordered binary tree (with duplicate elements)
NODE insert (int item, NODE root)
{
NODE temp, cur, prev;
temp = getnode( ); /* Obtain new node from the availability list */
temp->info = item; /* Copy appropriate data */
Data Structures using „C‟ Unit 6
Sikkim Manipal University Page No.: 191
temp->llink = NULL;
temp- >rlink = NULL;
if ( root = NULL ) return temp; /* Insert a node for the first time */
/* find the position to insert */
prev = NULL;
cur = root;
while ( cur != NULL )
{ /* Obtain parent and appropriate left or right child */
prev = cur;
cur = ( item < cur->info ) ? cur->llink : cur->rlink;
}
if ( item < prev->info ) /* If node to be inserted is less than parent */
prev->llink = temp; /* Insert towards left of the parent */
else
prev->rlink = temp; /* otherwise, insert towards right of the parent */
return root; /* Return the root of the tree */
}
In the above function duplicate items are inserted towards right. To avoid insertion of duplicate elements, the above function can be modified as shown in below example.
Note: In an ordered binary tree, the elements towards left of each node can be greater and elements towards right of each node can be less than or equal also.
Example : Function to insert an item into an ordered binary tree (No duplicate items are allowed)
NODE insert (int item, NODE root)
{
Data Structures using „C‟ Unit 6
Sikkim Manipal University Page No.: 192
NODE temp, cur, prev;
temp = getnode( ); /* Obtain new node from the availability list */
temp->info = item; /* Copy appropriate data */
temp->llink = NULL;
temp->rlink = NULL;
if ( root = = NULL) return temp; /* Insert a node for the first time */
/* find the position to insert */
prev = NULL;
cur = root;
while ( cur != NULL )
{ /* Obtain parent */
prev = cur;
/ * do not insert duplicate item */
if ( item = = cur->info )
{
printf("Duplicate items not allowed\n");
freenode(temp);
return root;
}
/* Find the appropriate left or right child */
cur = ( item < cur->info ) ? cur->llink : cur->rlink;
}
if ( item < prev->info ) /* If node to be inserted is less than parent */
rev->llink = temp; /* Insert towards left of the parent */
else
prev->rlink = temp; /* otherwise, insert towards right of the parent */
return root; /* Return the root of the tree */
}
Data Structures using „C‟ Unit 6
Sikkim Manipal University Page No.: 193
6.5.2 Searching
Start searching from the root node and move downward towards left or right based on whether the item lies towards left subtree or right subtree. This is achieved by comparing this item with root node of an appropriate subtree (left subtree or right subtree). If two items are same then search is successful and address of that node is returned. If the item is less than info (root), search in the left subtree, otherwise search in the right subtree. If item is not found in the tree, finally root points to NULL and return root indicating search is unsuccessful. The iterative function to search for this item is shown in below example.
Example Function to search for an item in BST using iteration
NODE iterative_ search (int item, NODE root)
{
/* search for the item */
while ( root != NULL && item != root->info )
{
root = ( item < root->info ) ? root->llink : root->rlink;
}
eturn root;
}
The recursive function to search for an item is shown in below example.
Example : Function to search for an item in BST using recursion
NODE recursive_ search (int item, NODE root)
{
if ( root = = NULL  item = = root->info ) return root;
if ( item < root->info ) return recursive_ search(item, root->llink);
return recursive_ search(item, root->rlink);
}
Data Structures using „C‟ Unit 6
Sikkim Manipal University Page No.: 194
6.5.3 Other operations
Other useful operations are shown below.
 find maximum -to return maximum item in the tree
 find minimum -to return minimum item in the tree
 to find height of the tree
 to count the number of nodes
 to count the leaf nodes
 deletion -deleting a node from the tree
6.5.3.1 To find maximum value in a tree BST
Given a binary search tree, a node with maximum value is obtained by traversing and the right most node in the tree. If there is no right subtree then return root itself as containing the item with highest value. The corresponding C function is shown in exam
Example : Function to return the address of highest item in BST
NODE maximum(NODE root)
{
NODE cur;
if ( root = = NULL) return root;
cur = root;
while ( cur->rlink != NULL) cur = cur->rlink; /* obtain right most node in BST */
return cur;
}
6.5.3.2 To find minimum value in a BST
Given a binary search tree, a node with least value is obtained by traversing and obtaining the let most node in the tree. If there is no left subtree then return root itself as the node containing a item with least value. The corresponding C function is shown in below example.
Data Structures using „C‟ Unit 6
Sikkim Manipal University Page No.: 195
Example : Function to return the address of least item in BST .
NODE minimum (NODE root)
{
NODE cur;
if ( root = = NULL) return root;
cur = root;
while ( cur->llink != NULL) cur = cur->llink; /* obtain left most node in BST */
return cur;
}
6.5.3.3 Height of tree
Height of the tree is nothing but the maximum level in a tree plus one. The recursive definition to find the height of the tree is
0 if root = NULL
Height(root) = 1 + max ( height(root->llink), height(root->rlink ) ) otherwise
The corresponding C function to find the height of this tree is shown in below example.
Example : Function to find the height of the tree .
/* function to find maximum of two numbers */
int max(int a, int b),
{
return ( a> b ) ? a: b;
}
/* Function to find the height of the tree */
int height(NODE root)
{
if ( root = = NULL) return 0;
Data Structures using „C‟ Unit 6
Sikkim Manipal University Page No.: 196
return 1 + max( height(root->llink), height(root->rlink));
}
6.5.3.4 Count nodes in a tree
The number of nodes in the tree is obtained by traversing the tree in any of the traversal technique and increment the counter whenever a node is visited. The variable count can be a global variable and it is initialed to zero to start with. In this example, the inorder traversal is used to visit each node. The C function to obtain the number of nodes in a tree is shown in below example.
Example : Function to count the number of nodes in a tree .
void count_ node(NODE root)
{
if ( root != NULL )
{
count_ node(root ->llink ) ;
count + +;
count_ node( root ->rlink);
}
}
6.5.3.5 Count leaves in a tree
As in the previous case visit each node in a given tree. Whenever a leaf is encountered update count by one. A leaf or a terminal node is one, which has an empty left and empty right child. The function to count the leaves in a binary tree is shown in below example. The variable count can be a global variable and it is initialed to zero to start with.
Example : Function to count the leaves or terminal nodes in a tree.
void count_ leaf (NODE root)
{
Data Structures using „C‟ Unit 6
Sikkim Manipal University Page No.: 197
if ( root != NULL )
{
count_ leaf(root->llink); /* Traverse recursively towards left */
/* if a node has empty left and empty right child ? */
if (root->llink = = NULL && root->rlink = = NULL )
count + +;
count_ leaf(root->rlink); /* Traverse recursively towards right */
}
}
6.5.3.6 Delete a node from the tree
To delete a node, we should search for the node to be deleted. If the required node is present, then that node has to be deleted. Otherwise, the message "Item not found" has to be displayed. The search for a node has been discussed earlier in section 6.5.2. It is very important to remember that once the required node is found and deleted, in a binary search tree the ordering of the tree should be maintained i.e., even after deleting a node, elements in the left subtree should be lesser and elements in the right subtree should be greater or equal. In a binary search tree the node to be deleted will have two cases:
1. An empty left subtree and nonempty right subtree or an empty right subtree and nonempty left subtree (A node having empty left child and empty right child is also deleted using this case).
2. Non empty left subtree and non empty right subtree
Case 1: Consider the figures shown in below fig: 6.9 (a) and (b) where cur denotes the node to be deleted and in both cases one of the subtrees is empty and the other is non-empty. The node identified by parent is the parent of the node cur. The non empty subtree can be obtained and is saved in a variable q. The corresponding code is:
if ( cur->llink == NULL) /* If leftsubtree is empty */
Data Structures using „C‟ Unit 6
Sikkim Manipal University Page No.: 198
q = cur->rlink; /* obtain the address of non empty right subtree */
else if ( cur->rlink == NULL) /* If right subtree is empty */
q = cur->llink; /* obtain the address of non empty left subtree */
Now, the non-empty subtree identified by q should be attached to the parent
of the node to be deleted and then delete the cur node. This is explained
immediately after case 2.
Case 2: Consider the figures shown in fig. 6-10 and fig. 6-11 where cur
denotes the node to be deleted. In both cases both the subtrees are nonempty.
The node identified by parent is the parent of the node cur. The node
can be easily deleted using the following procedure in sequence:
1. Find the inorder successor of the node to be deleted. The corresponding
code is:
suc = cur->rlink; /* lnorder successor always lies towards right */
while ( suc->llink != NULL) /* and immediately keep traversing left */
{
suc = suc->llink;
}
Data Structures using „C‟ Unit 6
Sikkim Manipal University Page No.: 199
2. Attach left subtree of the node to be deleted to the left of successor of the node to be deleted. The corresponding code is:
suc->llink = cur->llink; /* Attach left of node to be deleted to left of successor of the node to be deleted */
3. Obtain the right subtree of the node to be deleted. The corresponding code is:
q = cur->rlink; /* Right subtree is obtained */
4. Attach the right subtree of the node to be deleted to the parent of the node to be deleted.
This is explained as shown in the nex figure 6.10 and 6.11.
Data Structures using „C‟ Unit 6
Sikkim Manipal University Page No.: 200
Attach the node q to parent: If parent of the node to be deleted does not exist, then return q itself as the root node using the statement
if (parent = = NULL) return q;
If a parent exists for the node to be deleted, attach the subtree pointed to by q, to the parent of the node to be deleted. In this case, attach q to parent based on the direction. If cur is the left child, attach q to left (parent)
Data Structures using „C‟ Unit 6
Sikkim Manipal University Page No.: 201
otherwise attach q to right(parent). This can be achieved by using the following statement
/* connecting parent of the node to be deleted to q */
if( cur = = parent->llink )
parent->llink = q
else
parent->rlink = q;
Once the node q is attached to the parent, the node pointed to by cur can be deleted and then return the address of the root node. The corresponding statements are:
freenode (cur);
return root;
All these statements have been written by assuming the node to be deleted and its parent is known. So, just before deleting, search for the specified node, obtain its parent and then delete the node. The complete function to delete an item from the tree is shown in below example.
Example 1 : Function to delete an item from the tree
NODE delete_ item (int item, NODE root)
{
NODE cur, parent, suc, q;
if( root = = NULL)
{
printf("Tree is empty! Item not found\n");
return root;
}
/*obtain the position of the node to be deleted and its parent */
parent = NULL;
cur = root;
while ( cur != NULL && item != cur->info )
Data Structures using „C‟ Unit 6
Sikkim Manipal University Page No.: 202
{
parent = cur;
cur = ( item < cur->info ) ? cur->llink : cur->rlink;
}
if ( cur = = NULL)
{
printf("Item not found\n");
return root;
}
/* Item found and delete it */
*************************************************************/
/* CASE 1 */ *************************************************************/
if ( cur->llink = = NULL) /* If left subtree is empty */
q = cur->rlink; /* obtain the address of non empty right subtree */
else if ( cur->rlink = = NULL) /* If right subtree is empty */
q = cur->llink; /* obtain the address of non empty left subtree */
else
{
/************************************************/
/* CASE 2 */
/************************************************/
/* obtain the inorder successor */
suc = cur->rlink; /* Inorder successor lies towards right */
while (suc->llink != NULL) /* and immediately keep traversing left */
{
suc = suc->llink;
}
suc->llink = cur->llink; /* Attach left of node to be deleted to left */
Data Structures using „C‟ Unit 6
Sikkim Manipal University Page No.: 203
/* of successor of the node to be deleted */
q = cur->rlink; /* Right subtree is obtained */
}
/* If parent does not exist return q itself as the root */
if (parent = = NULL) return q;
/* connecting parent of the node to be deleted to q */
if ( cur = = parent->llink)
parent->llink = q;
else
parent->rlink = q;
freenode(cur);
return root;
}
The complete program for creating a tree, traversing and deleting a specified item is shown in below example
Example 2 : C program to create a tree, traverse a tree and delete a item from the tree
#include <stdio.h>
#include <alloc.h>
#include <process.h>
#include <string.h>
struct node
{
int info;
struct node *llink;
struct node *rlink;
};
typedef struct node* NODE;
Data Structures using „C‟ Unit 6
Sikkim Manipal University Page No.: 204
/* function to delete an item from the tree if it exists using above function example */
void main( )
{
NODE root, temp;
int choice, item;
root = NULL;
for (;;)
{
printf("1: delete 4: Exit\n");
printf("Enter the choice\n");
scanf("%d", &choice);
switch (choice )
{
case 1:
printf("Enter the item to be deleted\n");
scanf("%d",& item);
root = delete_ item(item, root);
break;
default:
exit(0);
}
}
}
Data Structures using „C‟ Unit 6
Sikkim Manipal University Page No.: 205
Self Assessment Questions:
1. Define BST with its common operations.
2. Explain the steps involves in insertion of item into BST.
6.6 Summary
The advantage of “Linked Lists” is that they solve the problem of sequential storage representation. But disadvantage in that is they are sequential lists. That is they are arranged so that it is necessary to move through item one after another sequentially to access a particular node. To overcome these problems of these sequential lists we will use data structure called “Trees”.
The binary search tree is organized in such a way that all of the items less than the item in a chosen node is contained in the left sub tree and all the items greater than the chosen node are contained in the right sub tree. In this manner one does not have to search the entire tree for a particular item in the manner of linked list traversals.
6.7 Terminal Questions
1. Define Tree ? Explain Binary tree with its properties.
2. Explain the storage representation of Binary tree with sequential representation of a tree.
3. List and describe the various operations on binary tree using linked representation.
4. Explain the types of algorithms for tree traversal.
5. Write a note on Binary Search Tree (BST).
6. Explain the two types of cases to delete node from tree.