Inorder Traversal of Binary Search Tree

 

To traverse a non-empty tree in inorder the following steps are followed recursively.

• Visit the Root
• Traverse the left subtree
• Traverse the right subtree

The inorder traversal of the tree shown below is as follows.

Algorithm



The algorithm for inorder traversal is as follows.


Struct node
{
struct node * lc;
int data;
struct node * rc;
};


void inorder(struct node * root);
{
if(root != NULL)
{
inorder(root-> lc);
printf("%d\t",root->data);
inorder(root->rc);
}
}


So the function calls itself recursively and carries on the traversal.

Binary search tree and its implementation

Binary tree

A tree is a finite set of nodes having a distinct node called root.

Binary Tree is a tree which is either empty or has at most two subtrees, each of the subtrees also being a binary tree. It means each node in a binary tree can have 0, 1 or 2 subtrees. A left or right subtree can be empty.

A binary tree is made of nodes, where each node contains a "left" pointer, a "right" pointer, and a data element. The "root" pointer points to the topmost node in the tree. The left and right pointers point to smaller "subtrees" on either side. A null pointer represents a binary tree with no elements -- the empty tree. The formal recursive definition is: a binary tree is either empty (represented by a null pointer), or is made of a single node, where the left and right pointers (recursive definition ahead) each point to a binary tree.

Representation of Binary Tree

The structure of each node of a binary tree contains one data field and two pointers, each for the right & left child. Each child being a node has also the same structure.

Struct node
{
struct node *lc ; /* points to the left child */
int data; /* data field */
struct node *rc; /* points to the right child */
}



1. Array Representation of Binary Tree: 

A single array can be used to represent a binary tree. 

For these nodes are numbered / indexed according to a scheme giving 0 to root. Then all the nodes are numbered from left to right level by level from top to bottom. Empty nodes are also numbered. Then each node having an index i is put into the array as its ith element. 

In the figure shown below the nodes of binary tree are numbered according to the given scheme. 

The figure shows how a binary tree is represented as an array. The root 3 is the 0 th element while its left child 5 is the 1 st element of the array. Node 6 does not have any child so its children ie 7 th & 8 th element of the array are shown as a Null value. 

It is found that if n is the number or index of a node, then its left child occurs at (2n + 1) th position & right child at (2n + 2) th position of the array. If any node does not have any child, then null value is stored at the corresponding index of the array.

/* Prorgram to implement the above array representation * /

Struct node
{
struct node * lc;
int data;
struct node * rc;
};
struct node * buildtree(int); /* builds the tree*/
void inorder(struct node *); /* Traverses the tree in inorder*/
int a[]={ 3,5,9,6,8,20,10,/0,/0,9,/0,/0,/0,/0,/0,/0,/0,/0,/0,/0,/0};


void main( )
{
struct node * root;
root= buildtree(0);
printf(“\n Inorder Traversal”);
inorder(root);
getch( );
}


struct node * buildtree(int n);
{
struct node * temp=NULL;
if( a[n] != NULL)
{
temp = (struct node *) malloc(sizeof(struct node));
temp-> lc=buildtree(2n + 1);
temp-> data= a[n];
temp-> rc=buildtree(2n + 2);
}
return temp;
}


void inorder(struct node * root);
{
if(root != NULL)
{
if(root!= NULL)
{
inorder(root-> lc);
printf(“%d\t”,root->data);
inorder(root->rc);
}
} 


Courtesy : NPTEL