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

Problem of the day

The height of a tree is equal to the number of nodes on the longest path from the root to a leaf.

You are given an arbitrary binary tree consisting of * 'n'* nodes where each node is associated with a certain value.

Find out the height of the tree.

```
Input: Let the binary tree be:
```

```
Output: 2
Explanation: The root node is 3, and the leaf nodes are 1 and 2.
There are two nodes visited when traversing from 3 to 1.
There are two nodes visited when traversing from 3 to 2.
Therefore the height of the binary tree is 2.
```

Detailed explanation

```
The first and only line contains the values of the tree’s nodes in the level order form ( -1 for NULL node). Refer to the example for further clarification.
Consider the binary tree:
```

```
The input of the tree depicted in the image above will be like:
1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1
Explanation :
Level 1 :
The root node of the tree is 1
Level 2 :
Left child of 1 = 2
Right child of 1 = 3
Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6
Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)
Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)
The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level, the second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level, and so on.
The input ends when all nodes at the last level are null (-1).
```

```
Print a single integer denoting the height of the given binary tree.
```

```
You do not need to print anything; it has already been taken care of. Just implement the given function.
```

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

```
2
```

```
The given tree is:
```

```
The root node is 3, and the leaf nodes are 1 and 2.
There are two nodes visited when traversing from 3 to 1.
There are two nodes visited when traversing from 3 to 2.
Therefore the height of the binary tree is 2.
```

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

```
3
```

```
The given tree is:
```

```
The root node is 3, and there is only one leaf node, which is 2.
All three nodes are visited while traversing from 3 to 2.
Therefore the height of the binary tree is 3.
```

```
2 -1 -1
```

```
1
```

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

```
1 <= 'n' <= 10000
Time Limit: 1 second
```