Inorder Traversal

Easy

0/40

Average time to solve is 32m

Contributed by

72 upvotes

Asked in companies

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].

Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1 :

1 2 3 -1 -1 -1  6 -1 -1

Sample Output 1 :

2 1 3 6

Explanation of Sample Output 1 :

The given binary tree is shown below:

Inorder traversal of given tree = [2, 1, 3, 6]

Sample Input 2 :

1 2 4 5 3 -1 -1 -1 -1 -1 -1

Sample Output 2 :

5 2 3 1 4

Explanation of Sample Output 2 :

The given binary tree is shown below:

Inorder traversal of given tree = [5, 2, 3, 1, 4]

Expected time complexity:

The expected time complexity is O(n).

Constraints :

1 <= 'n' <= 10^5
0 <= 'data' <= 10^5     

where 'n' is the number of nodes and 'data' denotes the node value of the binary tree nodes.

Time limit: 1 sec

Console