DATASTRUCTURES AND APPLICATIONS 21CS32

TABLE OF CONTENTS
1. Trees 1: Terminologies
2. Binary Trees, Properties of Binary trees
3. Array and linked Representation of Binary Trees
4. Binary Tree Traversals - Inorder, postorder, preorder
5. Threaded binary trees,
6. Binary Search Trees – Definition, Insertion, Deletion, Traversal, and Searching operation
on Binary search tree.
7. Application of Trees-Evaluation of Expression.

Textbook 1: Chapter 5: 5.1 –5.5, 5.7; Textbook 2: Chapter 7: 7.1 – 7.9

Textbooks:
1. Ellis Horowitz and Sartaj Sahni, Fundamentals of Data Structures in C, 2nd Ed,
Universities Press, 2014.
2. Seymour Lipschutz, Data Structures Schaum's Outlines, Revised 1st Ed, McGraw Hill,
2014.
3. Reema Thareja, Data Structures using C, 3rd Ed, Oxford press, 2012.

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING NIT RAICHUR

DATASTRUCTURES AND APPLICATIONS 21CS32

TREE DEFINITION :
A tree is a finite set of one or more nodes such that
 There is a specially designated node called root.
 The remaining nodes are partitioned into n >= 0 disjoint set T1,…,Tn, where each of
these sets is a tree. T1,…,Tn are called the subtrees of the root.

Every node in the tree is the root of some subtree

TERMINOLOGY
 Node: The item of information plus the branches to other nodes
 Degree of a node: The number of subtrees of a node
 Degree of a tree: The maximum of the degree of the nodes in the tree.
 Terminal nodes (or leaf): nodes that have degree zero or node with no successor
 Nonterminal nodes: nodes that don’t belong to terminal nodes.
 Parent and Children: Suppose N is a node in T with left successor S1 and right successor
S2, then N is called the Parent (or father) of S1 and S2. Here, S1 is called left child (or Son)
and S2 is called right child (or Son) of N.
 Siblings: Children of the same parent are said to be siblings.
 Edge: A line drawn from node N of a T to a successor is called an edge
 Path: A sequence of consecutive edges from node N to a node M is called a path.
 Ancestors of a node: All the nodes along the path from the root to that node.
 The level of a node: defined by letting the root be at level zero. If a node is at level l, then it
children are at level l+1.
 Height (or depth) of the tree: The maximum level of any node in the tree

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING NIT RAICHUR

DATASTRUCTURES AND APPLICATIONS 21CS32

A is the root node

B is the parent of E and F
C and D are the sibling of B
E and F are the children of B
K, L, F, G, M, I, J are external nodes, or leaves
A, B, C, D, E, H are internal nodes
The level of E is 3
The height (depth) of the tree is 4
The degree of node B is 2
The degree of the tree is 3
The ancestors of node M is A, D, H
The descendants of node D is H, I, J, M

Representation of Trees
There are several ways to represent a given tree such as:

Figure (A)

1. List Representation
2. Left Child- Right Sibling Representation
3. Representation as a Degree-Two tree

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING NIT RAICHUR

DATASTRUCTURES AND APPLICATIONS 21CS32

1. List Representation:

The tree can be represented as a List. The tree of figure (A) could be written as the list.
(A (B (E (K, L), F), C (G), D (H (M), I, J) ) )

 The information in the root node comes first.

 The root node is followed by a list of the subtrees of that node.

Tree node is represented by a memory node that has fields for the data and pointers to the
tree node's children

Since the degree of each tree node may be different, so memory nodes with a varying number of
pointer fields are used.
For a tree of degree k, the node structure can be represented as below figure. Each child field is
used to point to a subtree.

2. Left Child-Right Sibling Representation

The below figure show the node structure used in the left child-right sibling
representation

To convert the tree of Figure (A) into this representation:

1. First note that every node has at most one leftmost child

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING NIT RAICHUR

DATASTRUCTURES AND APPLICATIONS 21CS32

2. At most one closest right sibling.

Ex:
In Figure (A), the leftmost child of A is B, and the leftmost child of D is H.
The closest right sibling of B is C, and the closest right sibling of H is I.
Choose the nodes based on how the tree is drawn. The left child field of each node
points to its leftmost child (if any), and the right sibling field points to its closest right
sibling (if any).
Figure (D) shows the tree of Figure (A) redrawn using the left child-right sibling representation.

3. Representation as a Degree-Two Tree

To obtain the degree-two tree representation of a tree, simply rotate the right-sibling pointers in a
left child-right sibling tree clockwise by 45 degrees. This gives us the degree-two tree displayed
in Figure (E).

Figure (E): degree-two representation

In the degree-two representation, a node has two children as the left and right children.

BINARY TREES
Definition: A binary tree T is defined as a finite set of nodes such that,
• T is empty or

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING NIT RAICHUR

DATASTRUCTURES AND APPLICATIONS 21CS32

• T consists of a root and two disjoint binary trees called the left subtree and the right
subtree.

Figure: Binary Tree

Different kinds of Binary Tree

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 subtree or only right subtree.
 A tree with only left subtrees is called Left Skewed Binary Tree.
 A tree with only right subtrees is called Right Skewed Binary Tree.
2. Complete Binary Tree : 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 possible.

Figure (a): Skewed binary tree Figure (b): Complete binary tree

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

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING NIT RAICHUR

DATASTRUCTURES AND APPLICATIONS 21CS32

Figure: Full binary tree of level 4 with sequential node number

4. Extended Binary Trees or 2-trees : An extended binary tree is a transformation of any binary tree
into a complete binary tree. This transformation consists of replacing every null subtree of the original
tree with “special nodes.” The nodes from the original tree are then internal nodes, while the special
nodes are external nodes. For instance, consider the following binary tree.

The following tree is its extended binary tree. The circles represent internal nodes, and square represent
external nodes.Every internal node in the extended tree has exactly two children, and every external node
is a leaf. The result is a complete binary tree.
PROPERTIES OF BINARY TREES
Lemma 1: [Maximum number of nodes]:
1. The maximum number of nodes on level i of a binary tree is 2i-1, i ≥ 1.
2. The maximum number of nodes in a binary tree of depth k is 2k -1, k ≥ 1.

Proof:
(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 2i-1 = 20 = 1.
Induction Hypothesis: Let i be an arbitrary positive integer greater than 1. Assume that the maximum
number of nodes on level i -1is 2i-2
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, or 2i-1

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING NIT RAICHUR

DATASTRUCTURES AND APPLICATIONS 21CS32

(2) The maximum number of nodes in a binary tree of depth k is

k k
∑ (maximum number of nodes on level i) = ∑ 2i-1 = 2k-1
i=0 i=0

Lemma 2: [Relation between number of leaf nodes and degree-2 nodes]:

For any nonempty binary tree, T, if n0 is the number of leaf nodes and n2 the number of nodes of degree 2,
then n0 = n2 + 1.

Proof: Let n1 be the number of nodes of degree one and n the total number of nodes. Since all nodes in T
are at most of degree two, we have
n = n 0 + n 1+ n 2 (1)
Count the number of branches in a binary tree. If B is the number of branches, then n =B + 1.
All branches stem from a node of degree one or two. Thus,
B =n 1+ 2n2.
Hence, we obtain
n = B + 1= n 1+ 2n2 + 1 (2)

Subtracting Eq. (2) from Eq. (1) and rearranging terms, we get

n0 = n2 +1

Consider the figure:

Here, For Figure (b) n2=4, n0= n2+1= 4+1=5 Therefore, the
total number of leaf node=5

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING NIT RAICHUR

DATASTRUCTURES AND APPLICATIONS 21CS32

BINARY TREE REPRESENTATION

The storage representation of binary trees can be classified as
1. Array representation
2. Linked representation.

Array representation:
 A tree can be represented using an array, which is called sequential representation.
 The nodes are numbered from 1 to n, and one dimensional array can be used to store the nodes.
 Position 0 of this array is left empty and the node numbered i is mapped to position i of the array.
 Below figure shows the array representation for both the trees of figure (a).

• For complete binary tree the array representation is ideal, as no space is wasted.
• For the skewed tree less than half the array is utilized.

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING NIT RAICHUR

DATASTRUCTURES AND APPLICATIONS 21CS32

Linked representation:
The problems in array representation are:
 It is good for complete binary trees, but more memory is wasted for skewed and many other
binary trees.
 The insertion and deletion of nodes from the middle of a tree require the movement of many
nodes to reflect the change in level number of these nodes.

These problems can be easily overcome by linked representation

Each node has three fields,
 LeftChild - which contains the address of left subtree
 RightChild - which contains the address of right subtree.
 Data - which contains the actual information

C Code for node:

typedef struct node *treepointer;
typedef struct {
int data;
treepointer leftChild, rightChild;
}node;

Figure: Node representation

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING NIT RAICHUR

DATASTRUCTURES AND APPLICATIONS 21CS32

Linked representation of the binary tree

BINARY TREE TRAVERSALS

Visiting each node in a tree exactly once is called tree traversal.The different methods of traversing a
binary tree are:

1. Preorder
2. Inorder
3. Postorder

1. Inorder: Inorder traversal calls for moving down the tree toward the left until you cannot go
further. Then visit the node, move one node to the right and continue. If no move can be done,
then go back one more node. Let ptr is the pointer which contains the location of the node N
currently being scanned. L(N) denotes the leftchild of node N and R(N) is the right child of node
N

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING NIT RAICHUR

DATASTRUCTURES AND APPLICATIONS 21CS32

Recursion function:
The inorder traversal of a binary tree can be recursively defined as
• Traverse the left subtree in inorder.
• Visit the root.
• Traverse the right subtree in inorder.

void inorder(treepointer ptr)

{
if (ptr)
{
inorder (ptr→leftchild);
printf (“%d”,ptr→data);
inorder(ptr→rightchild);
}
}

2. Preorder: Preorder is the procedure of visiting a node, traverse left and continue. When you
cannot continue, move right and begin again or move back until you can move right and resume.

Recursion function:
The Preorder traversal of a binary tree can be recursively defined as
 Visit the root
 Traverse the left subtree in preorder.
 Traverse the right subtree in preorder

void preorder (treepointer ptr)

{
if (ptr)
{
printf (“%d”,ptr→data) ;
preorder (ptr→leftchild);
preorder (ptr→rightchild);

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING NIT RAICHUR

DATASTRUCTURES AND APPLICATIONS 21CS32

}
}

3. Postorder: Postorder traversal calls for moving down the tree towards the left until you can go
no further. Then move to the right node and then visit the node and continue.
Recursion function: The Postorder traversal of a binary tree can be recursively defined as Traverse the
left subtree in postorder.
 Traverse the right subtree in postorder.
 Visit the root

void postorder(treepointer ptr)

{
if (ptr)
{
postorder (ptr→leftchild);
postorder(ptr→rightchild);
printf (“%d”,ptr→data);
}
}

Traverse the Binary tree in all the pre-order,post-order and inorder

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING NIT RAICHUR

DATASTRUCTURES AND APPLICATIONS 21CS32

Construct a Binary using the following preorder and Inorder node representation

Pre-order 1,2,4,8,9,10,11,5,3,6,7
Inorder: 8,4,10,9,11,2,5,1,6,3,7

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING NIT RAICHUR

DATASTRUCTURES AND APPLICATIONS 21CS32

Construct a Binary using the following preorder and Inorder node representation

PRE-ORDER: A B D E F C G H L J K
INORDER: DBFEAGCLJHK
In pre order always root node will be at the beginning.so A will be choosen as root node

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING NIT RAICHUR

DATASTRUCTURES AND APPLICATIONS 21CS32

Inorder : { 4, 2, 1, 7, 5, 8, 3, 6 }
Postorder : { 4, 2, 7, 8, 5, 6, 3, 1 }
In post order always root node will be at the end.so 1 will be choosen as root node

ADDITIONAL BINARY TREE OPERATIONS

1. Copying a Binary tree : This operations will perform a copying of one binary tree to
another.

C function to copy a binary tree:

treepointer copy(treepointer original)

{
if(original)
{
MALLOC(temp,sizeof(*temp));
temp→leftchild=copy(original→leftchild);

temp→rightchild=copy(original→rightchild);
temp→data=original→data;
return temp;
}
return NULL;
}

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING NIT RAICHUR

DATASTRUCTURES AND APPLICATIONS 21CS32

2. Testing Equality : This operation will determine the equivalence of two binary tree.
Equivalence binary tree have the same structure and the same information in the
corresponding nodes.
C function for testing equality of a binary tree:

int equal(treepointer first,treepointer second)

{
return((!first && !second) || (first && second &&
(first→data==second→data) &&
equal(first→leftchild,second→leftchild) && equal(first→rightchild,
second→rightchild))
}
This function will return TRUE if two trees are equivalent and FALSE if they are not.

THREADED BINARY TREE

The limitations of binary tree are:
1. In binary tree, there are n+1 null links out of 2n total links.
2. 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.

We can represent a threaded binary tree in three ways.

1. One way Inorder Threading
2. Two way Inorder Threading
3. Two way Inorder Threading with header node

Inorder Traversal of a Binary tree is: D B F E A G C L J H K

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING NIT RAICHUR

DATASTRUCTURES AND APPLICATIONS 21CS32

Figure 1: One way Inorder Threading

Figure 2: Two way Inorder Threading

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING NIT RAICHUR

DATASTRUCTURES AND APPLICATIONS 21CS32

Figure 3: Two way Inorder Threading with header node

BINARY SEARCH TREE: Binary Search Tree is a binary tree.it may be empty. If it is not
empty then it satisfies the following properties.
1. Each node has exactly one key and keys are distinct.
2. The keys in the left sub-tree are smaller than the key in the root.
3. The keys in the right sub-tree are greater than the key in the root.
4. The left and right sub-tree are also binary search trees.
Example of BST

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING NIT RAICHUR

DATASTRUCTURES AND APPLICATIONS 21CS32

Searching a Binary Search Tree: Write a recursive C function of a binary Search Tree

element* search(treepointer root,int k){

if(!root)
return NULL
if(k==root->data.key)
return &(root->data);
if(k<root->data.key)
return search(leftchild,k);
return search(rightchild,k);
}

Searching a Binary Search Tree: Write a Iteraive C function of a binary Search Tree

element* search(treepointer root,int k){

while(tree){
if(k==root->data.key)
return &(root->data);
if(k<root->data.key)

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING NIT RAICHUR

DATASTRUCTURES AND APPLICATIONS 21CS32

tree=tree->leftchild;
else
tree=tree->rightchild;
}
return NULL;
}
Inserting into a BST: construct a BST for the following nodes given
Suppose the data elements are - 45, 15, 79, 90, 10, 55, 12, 20, 50

Write a C function for inserting a node into BST

void insert(treepointer *ndoe,int k,iType theItem){
treepointer ptr,temp=search(*node,k);
if(temp || !(*node)){
MALLOC(ptr,sizeof(*ptr);
ptr->data.key =k;

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING NIT RAICHUR

DATASTRUCTURES AND APPLICATIONS 21CS32

ptr->data.item = theItem;
ptr->leftChild = ptr->rightChild = NULL;
if(*node)
if(k<temp->data.key)
temp->leftChild=ptr;;
else
temp->rightChild=ptr;;
else
*node=ptr;
}
}
Deleting a node from a BST:

In a binary search tree, we must delete a node from the tree by keeping in mind that the property
of BST is not violated. To delete a node from BST, there are three possible situations occur -

1. The node to be deleted is the leaf node, or,

2. The node to be deleted has only one child, and,
3. The node to be deleted has two children

Case 1: delete a leaf node (90):

After deletion tree look like this:

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING NIT RAICHUR

DATASTRUCTURES AND APPLICATIONS 21CS32

Case 2: delete a node which contains one leaf(79): in place of parent node leaf node will be
replaced.

After deleting a parent node having one child tree look like as follows.

Case 3: Delete a node which contains two children (45):

 First, find the inorder successor of the node to be deleted.

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING NIT RAICHUR

DATASTRUCTURES AND APPLICATIONS 21CS32

 After that, replace that node with the inorder successor until the target node
is placed at the leaf of tree.
OR

 First, find the inorder predecessor of the node to be deleted.

 After that, replace that node with the inorder predecessor until the target
node is placed at the leaf of tree.
Example

Inorder treversal of the above tree is : 10 15 20 45 55 79

Inorder successor approach we choose 55 as the node to be replaced in place
of node 45

Expression tree: It is a tree used to represent algebraic expression into a binary tree.
Example 1; Construct a Binary tree
Question: a*b/c+e/f*g+k-x*y

1 2 6 3 4 7 8 5
A * B / C + E / F * G + K - X * Y

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING NIT RAICHUR

DATASTRUCTURES AND APPLICATIONS 21CS32

Example 2: Construct a Binary tree

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING NIT RAICHUR