# 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;
}``````
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

Scroll to Top