DATA STRUCTURES AND APPLICATIONS (21CS32)

Module 4-TREES
Terminologies, Binary Trees, Properties of
Binary trees, Array and linked
Representation of Binary Trees, Binary Tree
Traversals - Inorder, postorder, preorder;
Threaded binary trees, Binary Search Trees –
Module 4 Syllabus Definition, Insertion, Deletion, Traversal, and
Searching operation on Binary search tree.
Application of Trees-Evaluation of
Expression.

4.1 Tree Definition

Definition: A tree is a finite set of one or more nodes such that: (i) there is a specially designated node
called the root; (ii) the remaining nodes are partitioned into n>= 0 disjoint sets T1, ...,Tn where each of
these sets is a tree. T1, ...,Tn are called the sub-trees of the root.

Figure 4.1: Tree

4.1.1 Basic Terminology

 Root node : The root node R is the topmost node in the tree. If R = NULL, then it means the tree
is empty. Ex: A is the root node in Figure 4.1.
 Sub-trees: If the root node R is not NULL, then the trees T1 , T2 , and T3 are called the sub-trees
of R.
 Leaf node: A node that has no children is called the leaf node or the terminal node. Ex: E, F, J, K,
H and I are the leaf nodes in Figure 4.1.

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 1

 DATA STRUCTURES AND APPLICATIONS (21CS32)

 Non-terminals: The nodes other than leaf nodes are called non terminals. Ex: A, B, C, D, G are
non terminals in Figure 4.1.
 Path: A sequence of consecutive edges is called a path. For example, in Figure 4.1, the path from
the root node A to node I is given as: A, D, and I.
 Ancestor node: An ancestor of a node is any predecessor node on the path from root to that node.
The root node does not have any ancestors. In the tree given in Figure 4.1, nodes A, C, and G are
the ancestors of node K
 Descendant node: A descendant node is any successor node on any path from the node to a leaf
node. Leaf nodes do not have any descendants. In the tree given in Fig. Figure 4.1, nodes C, G, J,
and K are the descendants of node A.
 Degree of a node: Degree of a node is equal to the number of children that a node has. The degree
of a leaf node is zero.
 Level number: Every node in the tree is assigned a level number in such a way that the root node
is at level 1, children of the root node are at level number 2. Thus, every node is at one level higher
than its parent. So, all child nodes have a level number given by parent’s level number + 1.
 In-degree: In-degree of a node is the number of edges arriving at that node.
 Out-degree: Out-degree of a node is the number of edges leaving that node.
 Height of the tree: is the maximum distance between the root node of the tree and the leaf node of
the tree.(3 in our above example)
 Children : the roots of a sub-tree of node x are the children of x. Ex: E and F are the children of B.
 Siblings: children of same parent is called siblings. H and I are siblings in Figure 4.1.
 The degree of a tree : The degree of a tree is the maximum degree of the nodes in the tree. The
tree of Figure 4.1 has degree 3.

4.2. Binary Trees

 A binary tree is an important type of tree structure which occurs very often. It is characterized by
the fact that any node can have at most two branches, i.e., there is no node with degree greater than
two. For binary trees we distinguish between the sub-tree on the left and on the right, whereas for
trees the order of the sub-trees was irrelevant. Also a binary tree may have zero nodes. Thus a
binary tree is really a different object than a tree.
 Definition: A binary tree is a finite set of nodes which is either empty or consists of a root and two
disjoint binary trees called the left subtree and the right subtree.

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 2

 DATA STRUCTURES AND APPLICATIONS (21CS32)

 The distinctions between a binary tree and a tree should be analyzed. First of all there is no tree
having zero nodes, but there is an empty binary tree. The two binary trees in Fig. 4.2 are different.
The first one has an empty right subtree while the second has an empty left subtree. If the above
are regarded as trees, then they are the same despite the fact that they are drawn slightly
differently.

Fig. 4.2: binary trees example

4.2.1. Different kind Binary Trees:

1. Skewed Tree :A skewed tree is a tree, skewed to the left or skews to the right. or It is a tree
consisting of only left sub-tree or only right sub-tree. Figure 4.3(a) shows the sample of
skewed Tree.
 A tree with only left sub-trees is called Left Skewed Binary Tree.
 A tree with only right sub-trees is called Right Skewed Binary Tree.
2. A binary tree T is said to complete if all its levels, except possibly the last level, have the
maximum number node 2 i , i ≥ 0 and if all the nodes at the last level appears as far left as
[Link] 4.3b is called a complete binary tree. Notice that all terminal nodes are on
adjacent levels. The terms that we introduced for trees such as: degree, level, height, leaf.
parent, and child all apply to binary trees in the natural way.

Fig. 4.3: Two sample binary trees

3. Full Binary Tree: A full binary tree of depth ‘k’ is a binary tree of depth k having 2k – 1
nodes, k ≥ 1.

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 3

 DATA STRUCTURES AND APPLICATIONS (21CS32)

4.2.2 Properties of Binary Tree

Lemma 1& 2: [Maximum number of nodes]:

(1) The maximum number of nodes on level i of a binary tree is 2 i-1

, i ≥1.

(2) The maximum number of nodes in a binary tree of depth k is 2 k -1, k ≥ 1

Proof:

Step 1: The proof is by induction on i. Induction Base: The root is the only node on level i = 1.
Hence, the maximum number of nodes on level i =1 is 2 i-1 = 20 = 1.

Step 2: Induction Hypothesis: Let i be an arbitrary positive integer greater than 1. Assume that
the maximum number of nodes on level i -1 is 2i-2

Step 3: Induction Step: The maximum number of nodes on level i-1 is 2i-2 by the induction
hypothesis. Since each node in a binary tree has a maximum degree of 2, the maximum number of
nodes on level i is two times the maximum number of nodes on level i-1, i.e or 2*2i-2= 2i-1

(2) The maximum number of nodes in a binary tree of depth k is ∑𝒌𝒊=𝟏 = ∑𝒌𝒊=𝟏 𝟐𝒊−𝟏 =𝟐𝒌−𝟏

Lemma– 3:
For any nonempty binary tree, T, if no is the number of terminal nodes and n2 the
number of nodes of degree 2, then n0 = n2 + 1.
Proof:
Consider the binary tree in the Fig. 4.4. each node in the tree should have a maximum of 2
children. A node may not have any child or it can have single child or it can have 2 children.
But a node in a binary tree can not have more that 2 children.

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 4

 DATA STRUCTURES AND APPLICATIONS (21CS32)

Fig. 4.4: binary tree

Let No of nodes of degree 0 = n0
No of nodes of degree 1 = n1
No of nodes of degree 2 = n2
So total no. of nodes in the tree is = n0 + n1 + n2 ……………………………………..1
Observe from the tree that the total no of nodes is equal to the total no. of branches (B) plus 1
n = B+1 …………………………………………………………………………….2
if there is a node with degree 1, no. of branches = 1
so for n1, no. of nodes with degree 1, no. of branches = 1n1……………………….3
if there is a node with degree 2, no. of branches = 2
so for n2 , no. of nodes with degree 2, no. of branches = 2n2……………………….4
add 3 and 4, we get
B = 1n1 + 2n2 ………………………………………………………………………5
Substitute 5 in 2 we get
n = 1n1 + 2n2 + 1 ………………………………………………………………….6
from 1 and 6 we get
n0 + n1 + n2 = 1n1 + 2n2 + 1
=> n0 + n1 + n2 - 1n1 - 2n2– 1 = 0=> n0 - n2 – 1 =0=> n0 = n2 + 1
Hence it is proved that for any nonempty binary tree, T, if no is the number of terminal nodes and n2
the number of nodes of degree 2, then n0 = n2 + 1.

4.3 Binary Tree Representation

There are 2 ways of representations
1. Array representation
 If T is a binary tree, then it can be maintained in memory using sequential representation as
follows:
a. Root R of tree T is stored in TREE[1]
b. If a node n occupies TREE[k], then its left child is stored in TREE[2*k] and
right child is stored in TREE[2*k+1]
c. NULL is used to represent empty sub-tree
d. If TREE[1] is NULL, then it is an empty tree.
 Example is given in the Fig.4.5.

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 5

 DATA STRUCTURES AND APPLICATIONS (21CS32)

Fig.4.5: Example for array representation of binary tree

2. Linked representation:
 While the above representation appears to be good for complete binary trees it is wasteful
for many other binary trees. In addition, there presentation suffers from the general
inadequacies of sequential representations. Insertion or deletion of nodes from the middle
of a tree requires the movement of potentially many nodes to reflect the change in level
number of these nodes.
 These problems can be easily overcome through the use of a linked representation. Each
node will have three fields LCHILD, DATA and RCHILD as in Fig.4.6.

Fig.4.6: Linked representation of binary tree

 Ex: Consider a binary tree in the Fig. 4.7(a). The linked representation of this tree is given in the
Fig. 4.7.(b).it can be represented in the memory as shown in Fig.4.8.

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 6

 DATA STRUCTURES AND APPLICATIONS (21CS32)

Fig.4.7.: Example for Linked representation of binary tree

3.

Fig.4.8: memory representation of binary tree

4.4 Binary Tree Traversal

There are 3 types of binary tree traversal
4.4.1. Preorder traversal
To traverse a non-empty binary tree in pre-order, the following operations are performed recursively at
each node.
The algorithm works by:
1. Visiting the root node,
2. Traversing the left sub-tree, and finally
3. Traversing the right sub-tree.
Function code:
void preorder(struct treeNode *node)
{
if (node != NULL)
{
printf("%d", node->data);
preorder(node->left);
preorder(node->right);
}
return;
Prepared by Saritha Suvarna, Dept of CSE,CEC Page 7
 DATA STRUCTURES AND APPLICATIONS (21CS32)

}
4.4.2. Postorder traversal
To traverse a non-empty binary tree in post-order, the following operations are performed recursively
at each node. The algorithm works by:
1. Traversing the left sub-tree,
2. Traversing the right sub-tree.
3. Visiting the root node
Function code:
void postorder(struct treeNode *node)
{
if (node != NULL)
{
postorder(node->left);
postorder(node->right);
printf("%d", node->data);
}
return;
}
4.4.3. Inorder traversal
To traverse a non-empty binary tree in inorder, the following operations are performed recursively at
each node. The algorithm works by:
1. Traversing the left sub-tree,
2. Visiting the root node
3. Traversing the right sub-tree.

Function code:
void inorder(struct treeNode *node)
{
if (node != NULL)
{
inorder(node->left);
printf("%d", node->data);
inorder(node->right);
}
return;
}

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 8

 DATA STRUCTURES AND APPLICATIONS (21CS32)

4.5. Constructing a Binary Tree from Traversal Results

 We can construct a binary tree if we are given at least two traversal results.
 The first traversal must be the in-order traversal and the second can be either pre-order or post-
order traversal.
 The in-order traversal result will be used to determine the left and the right child nodes, and the
pre-order/post-order can be used to determine the root node.
Example1:In–order Traversal: DJHBEAFICG Post–order Traversal: JHDEBIFGCA
Construct the tree:
Step 1: Use the post-order sequence to determine the root node of the tree. The first
element would be the root node.
Step 2: Elements on the left side of the root node in the in-order traversal sequence
form the left sub-tree of the root node. Similarly, elements on the right side of the root
node in the in-order traversal sequence form the right sub-tree of the root node
Step 3: Recursively select each element from post-order traversal sequence and create
its left and right sub-trees from the in-order traversal sequence. Look at Fig.4.9 be
which constructs the tree from its traversal results. Now consider the in-order traversal
and post-order traversal sequences of a given binary tree.

Fig4.9:Construction of Binary Tree

Example 2:

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 9

 DATA STRUCTURES AND APPLICATIONS (21CS32)

Fig4.10: Construction of Binary Tree

4.6 Threaded Binary Trees

The limitations of binary tree are:

 In binary tree, there are n+1 null links out of 2n total links.
 Traversing a tree with binary tree is time consuming.
These limitations can be overcome by threaded binary tree
 In the linked representation of any binary tree, there are more null links than actual pointers.
These null links are replaced by the pointers, called threads, which points to other nodes in the
tree.
To construct the threads use the following rules:
 Assume that ptr represents a node. If ptr→leftChild is null, then replace the null link with a
pointer to the inorder predecessor of ptr.
 If ptr →rightChild is null, replace the null link with a pointer to the inorder successor of ptr.
Ex: Consider the binary tree as shown in below figure:

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 10

 DATA STRUCTURES AND APPLICATIONS (21CS32)

 There should be no loose threads in threaded binary tree. But in Figure B two threads have
been left dangling: one in the left child of H, the other in the right child of G.

 In above figure the new threads are drawn in broken lines. This tree has 9 node and 10 Null-
links which has been replaced by threads. When trees are represented in memory, it should be
able to distinguish between threads and pointers. This can be done by adding two additional
fields to node structure, ie., leftThread and rightThread
 If ptr→leftThread = TRUE, then ptr→leftChild contains a thread, otherwise it contains
apointer to the left child.
 If ptr→rightThread = TRUE, then ptr→rightChild contains a thread, otherwise it contains
pointer to the right child.
Node Structure: The node structure is given in C declaration

typedef struct threadTree *threadPointer

typedefstruct
{
short int leftThread;
threadPointer leftChild;
char data;
threadPointer rightChild;
short int rightThread;
}threadTree;

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 11

 DATA STRUCTURES AND APPLICATIONS (21CS32)

 The complete memory representation for the tree of figure is shown in Figure C .
 The variable root points to the header node of the tree, while root →leftChild points to the start
of the first node of the actual tree.
 This is true for all threaded trees. Here the problem of the loose threads is handled by pointing
to the head node called root.

4.8 Binary Search Tree

 Binary search trees (BST), sometimes called ordered or sorted binary trees, are a particular type
of containers: data structures that store "items" (such as numbers, names etc.) in memory. They
allow fast lookup, addition and removal of items, and can be used to implement either dynamic
sets of items, or lookup tables that allow finding an item by its key (e.g., finding the phone
number of a person by name).
 Binary search trees keep their keys in sorted order, so that lookup and other operations can use
the principle of binary search: when looking for a key in a tree (or a place to insert a new key),
they traverse the tree from root to leaf, making comparisons to keys stored in the nodes of the tree
and deciding, based on the comparison, to continue searching in the left or right subtrees. On
average, this means that each comparison allows the operations to skip about half of the tree, so
that each lookup, insertion or deletion takes time proportional to the logarithm of the number of
Prepared by Saritha Suvarna, Dept of CSE,CEC Page 12
 DATA STRUCTURES AND APPLICATIONS (21CS32)

items stored in the tree. This is much better than the linear time required to find items by key in
an (unsorted) array, but slower than the corresponding operations on hash tables.
 A binary search tree (Fig.4.11) T is a binary tree; either it is empty or each node in the tree
contains an identifier and:
(i) all identifiers in the left subtree of T are less (numerically or alphabetically) than the identifier
in the root node T;
(ii) all identifiers in the right subtree of T are greater than the identifier in the root node T;
(iii) the left and right subtrees of T are also binary search trees.

Fig.4.11: Binary Search tree

Structure:
struct node
{
int info;
struct node *llink;
struct node *rlink;
};
struct node* NODE;
4.8.1 Create Function
 First enter the data. If NODE=NULL, then create a new node using malloc function. Store the
data in that new node and make its left and right link as NULL.
NODE createNode(int item)
{
NODE newNode;
newNode = (NODE) malloc(sizeof (struct node));
newNode->info = item;

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 13

 DATA STRUCTURES AND APPLICATIONS (21CS32)

newNode->llink= NULL;
newNode->rlink = NULL;
return(newNode);
}
Example:
Create a binary search tree using the following data elements: 45, 39, 56, 12, 34, 78, 32, 10, 89, 54, 67,
81
Solution is given in Figure 4.12

.
.Figure 4.12 : Creating a Binary Search tree

4.8.2 Insert Function

The insert function is used to add a new node with a given value at the correct position in the binary
search tree. Adding the node at the correct position means that the new node should not violate the
properties of the binary search tree.
NODE insert(int item,NODE root)
{
NODE temp,cur,prev;
int i;
temp=getnode();
temp->info=item;
temp->llink=temp->rlink=NULL;

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 14

 DATA STRUCTURES AND APPLICATIONS (21CS32)

if(root==NULL)
{
root=temp;
return root;
}
else
{
prev=NULL;
cur=root;
while (cur!=NULL)
{
prev=cur;
cur=(temp->info<cur->info)?cur->llink:cur->rlink;
}
if(temp->info<prev->info)
prev->llink=temp;
else if(temp->info>prev->info)
prev->rlink=temp;
return root;
}
}

4.8.3 Search Function:

The search function is used to find whether a given value is present in the tree or not. The searching
process begins at the root node. The function first checks if the binary search tree is empty. If it is
empty, then the value we are searching for is not present in the tree. So, the search algorithm
terminates by displaying an appropriate message. However, if there are nodes in the tree, then the
search function checks to see if the key value of the current node is equal to the value to be searched.
If not, it checks if the value to be searched for is less than the value of the current node, in which case
it should be recursively called on the left child node. In case the value is greater than the value of the
current node, it should be recursively called on the right child [Link] procedure to find the node
with value 67 is illustrated in Fig. 4.13.

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 15

 DATA STRUCTURES AND APPLICATIONS (21CS32)

Fig4.13: Example for search an element in a Binary Search tree

NODE search(NODE root) /*for search function*/

{
int item,i=0;
NODE cur;
printf("enter the element to be searched\n");
scanf("%d",&item);
if(root==NULL)
{
printf("tree is empty\n");
return root;
}
cur=root;
while(cur!=NULL)
{
if(item==cur->info)
{
i++;
printf("Found key %d in tree\n",cur->info);
}
if(item<cur->info)

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 16

 DATA STRUCTURES AND APPLICATIONS (21CS32)

cur=cur->llink;
else
cur=cur->rlink;
}
if(i==0)
printf("Key not found\n");
return root;
}
4.8.4 Delete Function:
The delete function deletes a node from the binary search tree. However, utmost care should be taken
that the properties of the binary search tree are not violated and nodes are not lost in the process.
Case 1: Deleting a Node that has No Children
Look at the binary search tree given in Fig. 4.14. If we have to delete node 78, we can simply remove
this node without any issue. This is the simplest case of deletion.

Fig.4.14: delete a node that has no children in a Binary Search tree

Case 2: Deleting a Node with One Child
To handle this case, the node’s child is set as the child of the node’s parent. In other words, replace the
node with its child. Now, if the node is the left child of its parent, the node’s child becomes the left
child of the node’s parent. Correspondingly, if the node is the right child of its parent, the node’s child
becomes the right child of the node’s parent. Look at the binary search tree shown in Fig.4.15 and see
how deletion of node 54 is handled.

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 17

 DATA STRUCTURES AND APPLICATIONS (21CS32)
Fig.4.15: delete a node with one child in a Binary Search tree

Case 3: Deleting a Node with Two Children

To handle this case, replace the node’s value with its in-order predecessor (largest value in the left sub-
tree) or in-order successor (smallest value in the right sub-tree). The in-order predecessor or the
successor can then be deleted using any of the above cases. Look at the binary search tree given in
4.16 and see how deletion of node with value 56 is handled.

Fig.4.16: delete a node with 2 children in a Binary Search tree

4.9 Expression tree
 Expression tree is a binary tree in which each internal node corresponds to operator and each
leaf node corresponds to operand so for example expression tree for 3 + ((5+9)*2) would be:

 Inorder traversal of expression tree produces infix version of given postfix expression (same
with preorder traversal it gives prefix expression)
 Evaluating the expression represented by expression tree:
Let t be the expression tree
If t is not null then
If [Link] is operand then
Return [Link]
A = solve([Link])
B = solve([Link]) // calculate applies operator '[Link]' on A and B, and returns value
Return calculate(A, B, [Link])
Prepared by Saritha Suvarna, Dept of CSE,CEC Page 18
 DATA STRUCTURES AND APPLICATIONS (21CS32)

 Construction of Expression Tree

Now For constructing expression tree we use a stack. We loop through input expression and do
following for every character.
1) If character is operand push that into stack
2) If character is operator pop two values from stack make them its child and push current node
again. At the end only element of stack will be root of expression tree

Note: For problems kindly refer notes.

QUESTION BANK
1. Define the following
a. Tree h. Sibling
b. Node i. Grand parent
c. Root j. Degree of the tree
d. Degree k. Ancestor
e. Leaf nodes l. Level
f. Non terminals m. Depth of tree
g. Children
2. Define binary trees. Explain different properties of binary trees
3. Explain 2 types of representations of binary trees
4. Explain the traversing of binary trees
5. Determine inorder, preorder and postorder traversal of the following tree. Write the C-
routines

6. Suppose following sequence lists the node of binary tree in preorder and inorder
respectively, draw diagram of the tree:
Preorder: G B Q A C K F P D E R H
Inodrer: Q B K C F A G P E D H R
7. What is threaded binary tree? Explain with example
8. Define binary search tree. Explain different functions of binary search tree
9. Describe the binary search tree with an example. Write the iterative and recursive
function to search for a key value in a binary search tree
10. Write an expression tree for an expression i) A / B + C * D + E ii) ((6+(3-
2)*5)^2+3)
11. Construct the binary tree (B-tree) from the given traversals:

12. Construct a binary search tree for the inputs

i) 22, 14, 18, 50, 9, 15, 7, 6, 12, 32, 25
ii) 14, 5, 6, 2, 18, 20, 16, -1, 21

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 19

 DATA STRUCTURES AND APPLICATIONS (21CS32)

13. Explain and write the analysis of searching and inserting a node in BST.

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 20

 DATA STRUCTURES AND APPLICATIONS (21CS32)

Prepared by Saritha Suvarna, Dept of CSE,CEC Page 21