# Tree traversal

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.

1. Preorder
2. Inorder
3. Post order

#### 1. Inorder Traversal (Left-info-Right)

The inorder traversal of a non-empty binary tree is defined as follows

1. Traverse the left sub tree in inorder (left)
2. Visit the root node (info)
3. 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);

}

}

1. #### Preorder Traversal (info-left-right)

The preorder traversal of a non-empty binary tree is defined as follows

1. Visit the root node (Data)
2. Traverse the left sub tree in preorder (Left)
3. 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);

}

}

1. #### Postorder Traversal (Left-Right-info)

The postorder traversal of a non-empty binary tree is defined as follows

1. Traverse the left sub tree in postorder (Left)
2. Traverse the right sub tree in postorder (Right)
3. 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’

DS – Data structure Using C

OOP – Object Oriented Programming

Java Programming

DBMS – Database Management System

RDBMS – Relational Database Management System

Join Now: Data Warehousing and Data Mining