Given a binary tree, find height of it. Height of empty tree is -1, height of tree with one node is 0 and height of below tree is 3.
Example 1: Print height/depth of a Binary Tree
Input:
Output: Height: 3
Solutions
Method 1: Recursion
Height of a tree is the max [height of left-sub-tree, height of right-sub-tree] + 1, we can solve this problem with Recursion easily.
Calculate height of left and right sub-trees and return max (left, right)+1, the base condition would be - "-1" height for a null tree.
Complexity
The time complexity of this solution is O(n) and space complexity is O(n) due to recursive calls.