Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Problem of the day

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 the given binary tree:
```

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

Detailed explanation

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

```
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
```

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

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

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

```
2 1 3 6
```

```
The given binary tree is shown below:
```

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

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

```
5 2 3 1 4
```

```
The given binary tree is shown below:
```

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

```
The expected time complexity is O(n).
```

```
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
```