Binary Tree: Find the height - Recursive approach

Write a program to find the height of a binary tree using recursive approach

The height of the Binary Tree is defined as the number of edges in the longest path from the root to the leaf node

Edge Cases for height of the Binary Tree
- If the root is null, no nodes are present in the binary tree then the Height is -1
- If only one node is present i.e root then the Height is 0

In this problem we can divide the problem into smaller parts by using:
Height of Tree = 1 + MAX(Height of Left Subtree, Height of Right Subtree)
And then we further apply the same to the left subtree and to the right subtree till we reach the Base Case of the subtree being null and then we return -1

Note

There are various interpretations for height of a binary tree.
Some people consider height in terms of edges (the line connecting the two nodes) while other people consider the no of nodes in the longest path from root to leaf node.
And some people also consider levels to calculate height (root node is at level 1, its child nodes are at level 2 and the final leaf nodes are at level n, so the height becomes n)
So its important to call out how do you interpret the height of a binary tree

Here we are considering no of nodes in the longest path to calculate the BT height

Diagram

Algorithm

1. If current is NULL then simply return 0
2. Declare leftHeight as int and call heightOfTree function for current.left
3. Declare rightHeight as int and call heightOfTree function for current.right
4. Result will be the maximum of leftHeight and rightHeight
5. Return result

Complexity

Time Complexity : O(n) , where n is the number of nodes in binary tree
Space Complexity : O(Height of Tree)

The Time Complexity will be O(N) as visit every node once.
The space complexity will be O(Height of Tree) which is O(logN) for a perfect binary tree.
Its because of the stack memory consumed by the recursive calls

Java Code

class BinaryTreeMaxDepth{
 
        static class Node {
     
            int data;
            Node left, right;
     
            Node(int element) {
                data = element;
                left = right = null;
            }
        }
     
        Node root;
     
        public static Node constructBinaryTree(int[] arr, int i) {
            Node root = null;
            if (i < arr.length) {
                root = new Node(arr[i]);
     
                root.left = constructBinaryTree(arr, 2 * i + 1);
                root.right = constructBinaryTree(arr, 2 * i + 2);
            }
            return root;
        }
     
        public int heightofTree(Node current) {
            if (current == null)
                return 0;
            int leftHeight = heightofTree(current.left);
            int rightHeight = heightofTree(current.right);
     
            int result = Math.max(leftHeight, rightHeight) + 1;
            return result;
     
        }
     
        public static void main(String args[]) {
            BinaryTreeMaxDepth tt1 = new BinaryTreeMaxDepth();
     
            int[] btElements = new int[] { 50, 20, 30, 10, 200, 70, 90 };
            tt1.root = tt1.constructBinaryTree(btElements, 0);
            System.out.print("Height of given binary tree is : ");
            System.out.println(tt1.heightofTree(tt1.root));
     
        }
    
 }

Output

Height of given binary tree is : 3