The height of a binary tree is the length of the longest path from the root node to the deepest leaf node in the tree. It is also defined as the number of edges in the longest path from the root node to any leaf node in the tree. Generally height of the root node is considered as 0, height of it’s child nodes is 1 and so on.
But some other definitions consider the height of root node as 1, height of it’s child node as 2 and so on. We use this definition of binary tree height in the programming examples below.
Finding height of a binary tree Recursively
In order to write code to find height of a binary tree recursively, we need to think of the main problem in terms of similar smaller problems. For a given binary tree root node, let’s say we have the height of it’s left subtree as left_height and right subtree and right_height. Now the height of root node is equal to the maximum of left or right subtree height plus one (for the link between child subtree and root node).
We have the recursive equation as follows:
height(root) = max(height(root->left), height(root->right)) + 1
Below is the full code which finds maximum height of a binary tree using recursion.
Finding height of a binary tree Iteratively
Height of a binary tree is similar to total number of levels/layers present in a binary tree. So we can perform level order traversal of the binary tree and count the number of levels/layers processed in total.