Inorder Traversal In Binary Search Tree (BST)

Inorder traversing in binary search tree is a way of traversing in which we print the data of all nodes of a tree in increasing order.

Lets take an example of a tree which is shown as below :

For this tree if we will use the inorder traversal we are going to get the output following order :

1-4-6-7-9

Which is surprisingly is in increasing order by itself.

Let us see how to write the program for the same ( Inorder traversing in binary search tree) :

#include
 #include
 #include
 typedef struct node
 {
 int data;
 struct node* left;
 struct node* right;
 }node;
 node* newNode(int data)
 {
 node* p = (node*)malloc(sizeof(node));
 p->data = data;
 p->left = NULL;
 p->right = NULL;
 return(p);
 }
 void printInorder(node* p)
 {
 if (p == NULL)
 {
 return;
 }
 printInorder(p->left);
 printf("%d ", p->data);
 printInorder(p->right);
 }
 void main()
 {
 node *root = newNode(7);
 root->left = newNode(4);
 root->right = newNode(9);
 root->left->left = newNode(1);
 root->left->right = newNode(6);
 printf("\nInorder traversal of binary tree is \n");
 printInorder(root);
 getch();
 }
 

Now we have seen the program let’s understand this program bit by bit :

typedef struct node
 {
 int data;
 struct node* left;
 struct node* right;
 }node;

If we’ll talk about this particular piece of code. Here we have defined our own datatype using a structure. We have named that user-defined datatype as node using typedef. Here int data will be storing the value of the node which will be provided by the user. struct node* left; and struct node* right will be storing the addresses of the left and the right node respectively.

node* newNode(int data)
 {
 node* p = (node*)malloc(sizeof(node));
 p->data = data;
 p->left = NULL;
 p->right = NULL;
 return(p);
 }

As we all know that each and every function have some return type, in this function perticular function
node* newNode(int data) the return type is node * this is because if you’ll see at the end of the function the function is returning a value p which is of node * type. Here p is nothing but the address of the new node created. This fucntion is also having some argument which is int data. The values of the arguments will come from the the main function. The user will provide this data.

node* p = (node*)malloc(sizeof(node));

If we only define the structure of our user defined datatype (here it’s node) that would not be sufficient. We also have to provide the memory for the same datatype. So, here we are just allocating some memory to newly created node. By using the above line our new node p has been created.

p->data = data;

Through this line we are storing the value/data provided by the user into the node which is p in this case.

p->left = NULL;
 p->right = NULL;

Here we don’t have any left or right subtree so we are just providing the values as NULL to both left and right.

 

void printInorder(node* p)
 { 
if (p == NULL) 
{ 
return; 
}
 printInorder(p->left);
 printf("%d ", p->data);
 printInorder(p->right);
 }

This is the player function of the program. This function will do the inorder traversing in our binary tree. This function takes one argument which is root. After knowing the address of the root it can traverse he whole binary tree. The first thing it will check is the value of the node p. If very first node of the tree(root) is empty, then it means that the binary tree does not exist in the program. From thereafter the console returns back.

printInorder(p->left);

Here we are using recursion and we are calling the same function by itself. The function will call itself till the time it’ll meet the condition p==NULL. After it’ll meet the condition it will return back and then it’ll execute the following line :

printf("%d ", p->data);

Through this line we’ll get the data which is stored in the node which in turn contains the lowest values.

printInorder(p->right);

After printing the value this line will be executed and the process of recursion will be used again to print the values.

void main()
 {
 node *root = newNode(7);
 root->left = newNode(4);
 root->right = newNode(9);
 root->left->left = newNode(1);
 root->left->right = newNode(6);
 printf("\nInorder traversal of binary tree is \n");
 printInorder(root);
 getch();
 }

In this main function we are passing the vlaues in the newNode() to create the root and other left and right nodes.

node *root = newNode(7);

 

Here in newNode() we are passing the value 7. As the function newNode() will return a value as a new address this address will be cached in the root pointer. This will be used to pass the root in the printInorder() function. Which will print the whole tree.

 

root->left = newNode(4); 

root->right = newNode(9);

 root->left->left = newNode(1);

 root->left->right = newNode(6);

The above lines of code provides the values to the left and the right subtrees. At the end we call printInorder(root) so that was all for Inorder traversing in binary search tree.

if you liked this please conider sharing and subscribing to our blog

GET MORE STUFF LIKE THIS IN YOUR IN BOX
Subscribe to our mailing list and get interesting stuff and updates to your email inbox.
we respect your privacy so your id will not be shared
 

Leave a Reply

avatar
  Subscribe  
Notify of