Last Updated: 19 Jan, 2022

Inorder Traversal

Easy

Asked in companies

Solve now

Problem statement

You have been given a Binary Tree of 'n' nodes, where the nodes have integer values. Your task is to return the In-Order traversal of the given binary tree.

For example :

For the given binary tree:

The Inorder traversal will be [5, 3, 2, 1, 7, 4, 6].

Input Format :

The first line contains elements of the tree in the level order form.

The line consists of values of nodes separated by a single space. 

In case a node is null, we take -1 in its place.

Example :

The input for the above tree is:

1 3 8 5 2 7 -1 -1 -1 -1 -1 -1 -1

Explanation :

Level 1 :
The root node of the tree is 1

Level 2 :
Left child of 1 = 3
Right child of 1 = 8

Level 3 :
Left child of 3 = 5
Right child of 3 = 2
Left child of 8 = 7
Right child of 8 = null (-1)

Level 4 :
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 2 = null (-1)
Right child of 2 = null (-1)
Left child of 7 = null (-1)
Right child of 7 = null (-1)

1
3 8
5 2 7 -1
-1 -1 -1 -1 -1 -1

Output Format :

The output contains 'n' single space-separated integers denoting the node's values in In-Order traversal.

Note :

You don't need to print anything, it has already been taken care of. Just implement the given function.

Solve now

Approaches

01 Approach

As we can see, before processing any node, the left subtree is processed first, followed by the node, and the right subtree is processed at last. These operations can be defined recursively for each node. The recursive implementation is referred to as a Depth-first search (DFS), as the search tree is deepened as much as possible on each child before going to the next sibling.

The steps are as follows :

We create a recursive function inOrderHelper() which takes the root of the tree as an argument.
inOrderHelper() :
- Visit the left subtree of ‘node’ i.e., call inOrderHelper(‘node’ -> left).
- Visit ‘node’ and if ‘node’ != NULL then add data of node to answer.
- Visit the right subtree of ‘node’ i.e., call inOrderHelper(‘node’ -> right).

Solve now

02 Approach

To convert the above recursive procedure into an iterative one, we need an explicit stack.

The steps are as follows :

Create an empty stack and initialize the current node as root.
Run a loop until ‘CURRENT’ != NULL or stack is not empty:
- Push current node to stack and do ‘CURRENT’ = ‘CURRENT’ -> left until ‘CURRENT’ != NULL.
- Then pop the top node from the stack and add data from the popped node to answer.
- Then do ‘CURRENT’ = popped node -> right and go to step 2

Solve now

03 Approach

The idea here is to use Morris traversal for the Inorder traversal of the tree. The idea of Morris's traversal is based on the Threaded Binary Tree. In this traversal, we will create links to the predecessor back to the current node so that we can trace it back to the top of a binary tree. Here we don’t need to find a predecessor for every node, we will be finding a predecessor of nodes with only a valid left child.

So Finding a predecessor will take O( N ) as time as we will be visiting every edge at most two times and there are only ‘N’ - 1 edges in a binary tree. Here ‘N’ is the total number of nodes in a binary tree.

For more details, please check the Threaded binary tree and Explanation of Morris Method

The steps are as follows :

Create a new node, say ‘CURRENT’, and initialize it as ‘ROOT’.
Run a loop until ‘CURRENT’ !=NULL and do:
- If CURRENT -> left = NULL then add data of current to answer and do CURRENT = CURRENT -> right
- Else In current’s left subtree, make ‘CURRENT’ as of the right child of rightmost node and visit this left child i.e. CURRENT = CURRENT -> left.

Solve now