Binary Trees
Bharat Gupta
Data structures
Data structure is a specialized format for
organizing and storing data.
Types:
1. Linear data structures: elements are accessed in a
sequential order
2. Non-linear data structures: elements are
stored/accessed in a non-linear order.
Bharat Gupta
1
Tree
Non-linear data structures
Each node points to a number of nodes.
Representing the hierarchical nature of a
structure in a graphical form.
Bharat Gupta
Bharat Gupta
2
Hierarchical Data Structures
One-to-many relationship between elements
Tree
Single parent, multiple children
Binary tree
Tree with 02 children per node
Tree Bharat Gupta Binary Tree
Root: node with no parents
Edge: link from parent to child
Leaf: node with no children
Depth: depth of a node is the length of the path
from the root node to the leaf.
Level: set of all nodes at a given depth. Root
(level-0)
Bharat Gupta
3
Bharat Gupta
Height (node): length of the path from the node
to the deepest node.
Height (tree): MAXIMUM height among all the
nodes in the tree
Size: size of a node is the number of
descendents it has including itself.
Bharat Gupta
4
Skew trees: if every node of a tree has only one
child (except leaf nodes)
Bharat Gupta
Binary tree
A tree is called as binary tree if each node has
zero child, 1 child, 2 childs.
Bharat Gupta
5
Bharat Gupta
Binary tree types
Strict binary tree: if each node has exactly 2 or
no children.
Bharat Gupta
6
Full binary tree: each node has exactly 2
children and all leaf nodes are at same level.
Bharat Gupta
Complete binary tree:if all leaf nodes are at
height h or h-1
Bharat Gupta
7
Properties of binary tree
Number of nodes in a full binary tree is 2h+1 -1
Complete binary tree: 2h to 2h+1 -1
Leaf nodes (full binary tree): 2h
Bharat Gupta
Trees
Terminology
Root no predecessor
Leaf no successor
Interior non-leaf
Height distance from root to leaf
Root node
Interior nodes Height
Leaf nodes
Bharat Gupta
8
Structure of binary tree
Bharat Gupta
Operations on Binary tree
Bharat Gupta
9
Applications of Binary Trees
Expressions tree in compliers
Hoffman coding trees
Binary Search Tree
Priority trees
Bharat Gupta
Binary Tree traversals
Process of visiting all nodes of a tree is known
as tree traversal.
Bharat Gupta
10
Traversal possibilities
Current node/root (D)
Left child node (L)
Right child node ( R)
Traversal possibilities
LDR (Inorder traversal)
DLR (Preorder traversal)
LRD (Postorder traversal)
Bharat Gupta
Bharat Gupta
11
Preorder traversal
Visit the root.
Traverse the left subtree in Preorder.
Traverse the right subtree in Preorder.
1 2 4 5 3 6 7
Bharat Gupta
Structure of binary tree
Bharat Gupta
12
void PreOrder ( struct BinaryTreeNode * root)
{
if (root)
{ printf (%d, rootdata);
PreOrder (rootleft);
PreOrder (rootright);
}
}
Bharat Gupta
Inorder traversal
Traverse the left subtree in Inorder.
Visit the root.
Traverse the right subtree in Inorder.
4 2 5 1 6 3 7
Bharat Gupta
13
void InOrder ( struct BinaryTreeNode * root)
{
if (root)
{ InOrder (rootleft);
printf (%d, rootdata);
InOrder (rootright);
}
}
Bharat Gupta
PostOrder traversal
Traverse the left subtree in Postorder.
Traverse the right subtree in Postorder.
Visit the root.
4 5 2 6 7 3 1
Bharat Gupta
14
void PostOrder ( struct BinaryTreeNode * root)
{
if (root)
{ PostOrder (rootleft);
PostOrder (rootright);
printf (%d, rootdata);
}
}
Bharat Gupta
Level order traversal
Visit the root.
While traversing level l, keep all the elements at level
l+1 in queue.
Go to the next level and visit all the nodes at that level.
Repeat this until all levels are completed.
1 2 3 4 5 6 7
Bharat Gupta
15
Inorder traversal
Traverse the left subtree in Inorder.
Visit the root.
Traverse the right subtree in Inorder.
4 2 5 1 6 3 7
Bharat Gupta
Binary tree array based implementation
#include<stdio.h>
int arr[100],count;
main()
{ int i,num,choice;
count = 0;
for(i=0;i<100;i++)
arr[i] = 0;
do
{
printf("enter your choice \n 1.Insert into tree \n
2.delete from tree \n 3. search for an element in tree
\n 4. inorder traversal\n5. exit\n");
scanf("%d",&choice);
Bharat Gupta
16
switch(choice)
{
case 1:
printf("enter element");
scanf("%d",&num);
arr[count] = num;
count++;
break;
Bharat Gupta
case 2:
printf("\n enter the element to be deleted");
scanf("%d",&num);
for(i=0;i<count;i++)
{
if(arr[i]==num) {
count--;
arr[i] = arr[count];
arr[count] = 0;
break;}
}
if(i==count)
printf("\n element not found");
break;
Bharat Gupta
17
case 3:
printf("\n enter the element to be searched");
scanf("%d",&num);
for(i=0;i<count;i++)
{ if(arr[i]==num) {
printf("\n element found");
break; }
}
if(i==count)
printf("\n element not found");
break;
Bharat Gupta
case 4:
inorder(0);
break;
}
}while(choice != 5);
Bharat Gupta
18
Binary tree array based implementation
void inorder(int pos)
{ int i,j;
i = 2*pos + 1;
if(arr[i] != 0)
inorder(i);
printf("\t %d",arr[pos]);
j = 2*pos +2;
if(arr[j] != 0)
inorder(j);
}
4 2 5 1 6Bharat Gupta3 7
Problems
Searching an element in a binary tree
Find (struct BinaryTreeNode * root, int data)
{ int temp;
if (root==NULL) return 0;
else
{ if (data==rootdata)
return 1;
else {
temp= Find(rootleft, data);
if (temp!=0)
return temp;
else
return Find(rootright, data);} }
Bharat Gupta
return 0;}
19
