In-Order Traversal

What is in-order Traversal ?  And its implementation

Traversal

Traversal is a process to all the nodes of a tree. Generally, we traverse a tree to Search or to print all the values it Contains.

In-order Traversal

In this method, we visit the left subtree first, then the root and then the right subtree (Every node can be a subtree). We use recursive method.
So, first we traverse the left subtree recursively. we call In-order(left-subtree). Then we visit the root (Visiting means Printing in this context), and then we call In-order(right-subtree).

Algorithm

Step 1 : Recursively traverse the left-subtree till it reach the leaf. Do this by calling function In-order(left-subtree).

Step 2 : Visit the root node. we will print value here.

Step 3 : Recursively traverse the right-subtree till it reach the leaf. Do this by calling In-order(right-subtree).

Note : Here In-order(left-subtree) calls again In-order(left-subtree) and In-order(right-subtree) it goes until node null.

Do this until all the nodes are traversed and printed.

Example

 Figure : Binary tree

Figure : In-order applied on binary tree

In this diagram, Algorithmstarts with A then goes to the left-subtree that is B then D and It reaches F (left most node or subtree) prints it, then visits its root D prints it and finally goes to right-subtree. This process goes on until all the nodes are visited.

Output : F->D->G->B->E->A->H->C->I

C++ Program

#include <stdio.h>
#include <stdlib.h>
 
/* implementing binary tree with pointers to left child node and right child node*/
struct node
{
     char data;
     struct node* left;
     struct node* right;
};
/*In this function we are creating a node with the given data and null left and right pointers  */ 
struct node* newNode(char data)
{
     struct node* node = (struct node*)
                                  malloc(sizeof(struct node));
     node->data = data;
     node->left = NULL;
     node->right = NULL;
     return(node);
}

/*This is the recursive function for inorder traversal*/
void InorderTraversal(struct node* node)
{
     if (node == NULL)
          return;
     InorderTraversal(node->left);/*Recrsion on Left sub-tree*/
     printf("%c ", node->data); /*printing data of the node*/
     InorderTraversal(node->right); /*Recursion on Right sub-tree*/
}
 
 
/*main fuction to test the code*/
int main()
{
     /*Here we are creating a tree by inserting elements*/
     struct node *root  = newNode('A');
     root->left             = newNode('B');
     root->right           = newNode('C');
     root->right->left     = newNode('H');
     root->right->right      = newNode('I');
     root->left->left     = newNode('D');
     root->left->left->left     = newNode('F');
     root->left->left->right     = newNode('G');
     root->left->right   = newNode('E'); 
     
     printf("\nIn-order traversal of the given input binary tree is : \n" );
     InorderTraversal(root);  
     return 0;
}
Try It
Time complexity : O(n)

Let Complexity function be : C(n)

Number of nodes one side of the root be m So,
C(n) = C(m) + C(n-m-1)

Case 1

If m = 0,
C(n) = C(0) + C(n-1) + c
We know, C(n-1) = C(0) + C(n-2) + c
Therefore,
C(n) = 2C(0) + C(n-2) + 2c
C(n) = 3C(0) + C(n-3) + 3c
C(n) = 4C(0) + C(n-4) + 4c
….…………………………………
C(n) = nC(0) + nc
C(n) = n(c + C(0))
C(0) will be some constant p
C(n) = n(c+p)
C(n) =Θ(n) (Theta of n)

Case 2

If left and right have equal number of nodes, then
C(n) = 2 X C(n/2) + c
By using master theorem ,
We get C(n) = Θ(n)

Therefore, Time complexity = O(n)

Space Complexity

O(h)
h = Height of the tree


Next > < Prev
Scroll to Top