Last Updated: 22 Apr, 2022
Height of Binary Tree
Easy
Asked in companies
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.
Example :
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.
Input Format :
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).
Output Format :
Print a single integer denoting the height of the given binary tree.
Note :
You do not need to print anything; it has already been taken care of. Just implement the given function.
Approaches
To find the depth of the tree, We will do the DFS on the tree starting from the root node.
In DFS, we visit all the nodes (child and grandchild nodes) of one child node before going to the second child node, which will help us determine the tree's height. We will take the maximum of both the child’s height.
We will go to the left node and increase one if it is not NULL and do DFS on the left node, the similar thing we will do on the correct node and return the max of the left and right node.
The steps are as follows:
heightOfBinaryTree(TreeNode 'root'):
- If 'root' is NULL:
- Return 0, because it is not counted as a node.
- Else:
- Initialize ‘depthLeft’ = heightOfBinaryTree(root.left ).
- Initialize ‘depthRight’ = heightOfBinaryTree(root.right ).
- We take the maximum of both the depth because height is the maximum number of edges encountered from the root to one or more leaf nodes.
- If depthLeft > depthRight:
- Return ‘depthLeft + 1’.
- Else:
- Return ‘depthRight + 1’.
- We add the +1 on each node call to represent the edge connecting the current node to that child node.
BFS stands for Breadth-first search, where we visit every node on each level before going to the next level.
By level, I mean that the root is at level 1, then all its children will be on level 2, their children will be on level 3, and so on.
In the level-order traversal, we will check all the nodes at the same level together to maintain the number of levels.
The steps are as follows:
heightOfBinaryTree(TreeNode 'root'):
- If 'root' is NULL:
- Return 0.
- Let 'q' be a queue storing the tree nodes.
- Insert 'root' in 'q'.
- Let 'height' = 0 be the answer variable.
- While 'q' is not empty:
- Let 'count' be the number of nodes in 'q'. This is basically storing the number of nodes at the current level.
- Run a loop 'count' times:
- Pop the front node from 'q' and store it in 'node'.
- Insert the children of 'node' in 'q', obviously if they exist.
- 'height' = 'height' + 1
- Return 'height'