In this article tree traversal we give the information about Traversing a tree means visiting all its nodes exactly once in a systematic manner to get the complete tree information.
Tree traversal
Traversing a tree is one of the important operations performed on tree. Traversing a tree means visiting all its nodes exactly once in a systematic manner to get the complete tree information. There are three methods of binary tree traversal.
- Preorder
- Inorder
- Post order
1. Inorder Traversal (Left-info-Right)
The inorder traversal of a non-empty binary tree is defined as follows
- Traverse the left sub tree in inorder (left)
- Visit the root node (info)
- Traverse the right sub tree in inorder (right)
In inorder traversal, the left sub tree is traversed recursively in inorder before visiting the root node. After visiting the root node, the right sub tree is traversed recursively again in inorder.
The inorder traversal of above binary tree is D B H E A G C G I
The function for recursive inorder traversing is given below:
void inorder(NODE root)
{
NODE temp=root;
if(temp!=NULL)
{
inorder(temp->left);
printf(“%d”,temp->info)
inorder(temp->right);
}
}
-
Preorder Traversal (info-left-right)
The preorder traversal of a non-empty binary tree is defined as follows
- Visit the root node (Data)
- Traverse the left sub tree in preorder (Left)
- Traverse the right sub tree in preorder (Right)
In preorder traversal, root node is visited first before traversing left and right sub tree. Then left sub tree is traversed recursively in preorder and then right sub tree is traversed recursively again in preorder.
The preorder traversal of above binary tree is A B D E H C F G I
The function for recursive preorder traversing is given below:
void preorder(NODE root)
{
NODE temp=root;
if(temp!=NULL)
{
printf(“%d”, temp->info)
preorder(temp->left);
preorder(temp->right);
}
}
-
Postorder Traversal (Left-Right-info)
The postorder traversal of a non-empty binary tree is defined as follows
- Traverse the left sub tree in postorder (Left)
- Traverse the right sub tree in postorder (Right)
- Visit the root node (Data)
In postorder traversal, first left sub tree is traversed recursively in postorder. Then right sub tree is traversed recursively in postorder. Finally the root node is visited.
The postorder traversal of above binary tree is D H E B F I G C A
The function for recursive postorder traversing is given below:
void postorder(NODE root)
{
NODE temp=root;
if(temp!=NULL)
{
preorder(temp->left);
preorder(temp->right);
printf(“%d”,temp->info);
}
}
Program:
Following program creates binary tree and traverse the same in inorder, preorder and post order methods.
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct node
{
int info;
struct node *left;
struct node *right;
};
typedef struct node *NODE;
NODE root=NULL;
int count=1;
void main()
{
int Opt,data;
NODE Insert(NODE, int);
void Inorder(NODE);
void Preorder(NODE);
void Postorder(NODE);
while(1)
{
printf(“\n 1: Create Tree”);
printf(“\n 2: Inorder”);
printf(“\n 3: Preorder”);
printf(“\n 4: Postorder”);
printf(“\n 5: Exit”);
printf(“\n Enter option: ”);
scanf(“%d”,&Opt);
switch(Opt)
{
case 1:
printf(“\n Enter Data: ”);
scanf(“%d”,&data);
root=Insert(root,data);
break;
case 2:
printf(“\n—-INORDER—-”);
Inorder(root);
break;
case 3:
printf(“\n—-PREORDER—-”);
Preorder(root);
break;
case 4:
printf(“\n—-POSTORDER—-”);
Postorder(root);
break;
case 5:
exit(0);
default:
printf(“\n Enter correct option”);
}
}
}
NODE Insert(NODE NewNode, int data)
{
if(NewNode==NULL)
{
NewNode=(NODE)malloc(sizeof(NODE));
NewNode->left=NewNode->right=NULL;
NewNode->info=data;
count++;
}
else
If(count%2==0)
NewNode->left=Insert(NewNode->left,data);
else
NewNode->right=Insert(NewNode->right,data);
return(NewNode);
}
void Inorder(NODE root)
{
NODE temp=root;
if(temp!=NULL)
{
Inorder(temp->left);
printf(“\n %d”,temp->info);
Inorder(temp->right);
}
}
void Preorder(NODE root)
{
NODE temp=root;
if(temp!=NULL)
{
printf(“\n %d”,temp->info);
Preorder(temp->left);
Preorder(temp->right);
}
}
void Postorder(NODE temp)
{
if(temp!=NULL)
{
Postorder(temp->left);
Postorder(temp->right);
printf(“\n %d”,temp->info);
}
}
Binary Search Tree
A binary search tree is a binary tree whose all data in the left subtree are less than root data, and all data in the right sub tree are greater than root data. The right and left subtree are also binary search trees.
The following steps are to create a binary search tree
Step 1 Initially, root=NULL
Step 2 Create a node newNode and store a data
Step 3 If root=NULL, Assign newNode to root and go to step 6
Step 4 Let temp=root
Step 5 If data<temp->data
If temp does not have a left child
attach to new node to temp->left
Goto 6
Else
Temp=temp->left
Goto 5
Else
If temp does not have left child
attach newnode to temp->right
Goto 6
Else
Temp=temp->right
Goto 5
Step 6 Repeat from step 2 till all data have been inserted in to the tree
Step 7 Stop
Following figure shows binary search tree.
Program:
Following program creates binary search tree and traverse the same in inorder, preorder and post order methods.
#include<stdio.h>
#include<conio.h>
struct node
{
int info;
struct node *left;
struct node *right;
};
typedef struct node *NODE;
NODE root=NULL;
void main()
{
int Opt,data;
NODE Insert(NODE, int);
void Inorder(NODE);
void Preorder(NODE);
void Postorder(NODE);
while(1)
{
printf(“\n 1: Create Tree”);
printf(“\n 2: Inorder”);
printf(“\n 3: Preorder”);
printf(“\n 4: Postorder”);
printf(“\n 5: Exit”);
printf(“\n Enter option: ”);
scanf(“%d”,&Opt);
switch(Opt)
{
case 1:
printf(“\n Enter Data: ”);
scanf(“%d”,&data);
root=Insert(root,data);
break;
case 2:
printf(“\n —-INORDER—-”);
Inorder(newNode)
break;
case 3:
printf(“\n —-PREORDER—-”);
Preorder(newNode);
break;
case 4:
printf(“\n —-POSTORDER—-”);
Postorder(newNode);
break;
Case 5: exit(0);
default: printf(“\n Enter correct option”);
}
}
}
NODE Insert(NODE temp, int data)
{
if(temp==NULL)
{
temp=(NODE)malloc(sizeof(NODE));
temp->left=temp->right=NULL;
temp->info=data;
}
else
if(data<temp->info)
temp->left=Insert(temp->left,data);
else
if(data>temp->info)
temp->right=Insert(temp->right,data);
else
printf(“\n Node is already present”);
return(temp);
}
void Inorder(NODE root)
{
NODE temp=root;
if(temp!=NULL)
{
Inorder(temp->left);
printf(“\n %d”,temp->info);
Inorder(temp->right);
}
}
void Preorder(NODE root)
{
NODE temp=root;
if(temp!=NULL)
{
printf(“\n %d”,tepm->info);
Preorder(temp->left);
Preorder(temp->right);
}
}
void postorder(NODE root)
{
NODE temp=root;
if(temp!=NULL)
{
Postorder(temp->left);
Postorder(temp->right);
printf(“\n %d”,temp->info);
}
}
Program:
Following program creates binary search tree and search whether given data is present in the tree or not.
#include<stdio.h>
#include<conio.h>
struct node
{
int info;
struct node *left;
struct node *right;
};
typedef struct node *NODE;
NODE root=NULL;
void main()
{
int Opt,data;
NODE Insert(NODE, int);
void Inorder(NODE);
void SearchNode(NODE, int);
while(1)
{
printf(“\n 1: Create Tree”);
printf(“\n 2: Search”);
printf(“\n 3: Traverse”);
printf(“\n 4: Exit”);
printf(“\n Enter Option: ”);
scanf(“%d”,&Opt);
switch(Opt)
{
case 1:
printf(“\n Enter data: ”);
scanf(“%d”,&data);
root=Insert(root,data);
break;
case 2:
printf(“\n Enter data for Search: ”);
scanf(“%d”,&data);
SearchNode(root,data);
break;
Case 3:
Inorder(root);
Break;
Case 4:
exit(0);
default:
printf(“\n Enter correct option”);
}
}
}
NODE Insert(NODE root, int data)
{
NODE temp=root;
if(temp==NULL)
{
temp=(NODE)malloc(sizeof(NODE));
temp->left=temp->right=NULL;
temp->info=data;
}
else
if(data<temp->info)
temp->left=Insert(temp->left,data);
else
if(data>temp->info)
temp->right=Insert(temp->right,data);
else
printf(“\n Node is already present”);
return(temp);
}
void Inorder(NODE root)
{
NODE temp=root;
if(temp!=NULL)
{
Inorder(temp->left);
printf(“\n %d”,temp->info);
Inorder(temp->right);
}
}
void SearchNode(NODE root, int data)
{
NODE temp=root;
if(temp==NULL)
printf(“\n Number is Not Present”);
else
if(data==temp->info)
printf(“\n Number %d is present in the tree”,data);
else
if(data<temp->info)
SearchNode(temp->left,data);
else
SearchNode(temp->right,data);
}
Some More:
POP- Introduction to Programming Using ‘C’
OOP – Object Oriented Programming
DBMS – Database Management System
RDBMS – Relational Database Management System
Join Now: Data Warehousing and Data Mining