Height of Binary Tree - Recursive

In this tutorial, we will see how to find the height of a binary tree or how to find maximum depth of a binary tree using recursion. Let us firstly understand the definition of height of binary tree.
Height of Binary Tree: A binary tree's maximum depth/height is the number of nodes along the longest path from the root node down to the farthest leaf node.
Let us take the following example:

The height of the above tree is: 3

Explanation:

1. We will start calculating the height of a tree from root.
2. We will give two recursive calls one to the left of the tree and one to the right of tree.
3. The left call will give us height of the leftSubTree and right call will give us height of a rightSubTree and at last we will return maximum of (left, right) + 1.
4. Here 1 is included as the height of a node.
Here we have taken the height of an empty tree as 0 (i.e root == null).

Algorithm:

1. if root == null return 0
2. call left of the tree and store value in left (root.left)
3. call right of the tree and store value in right (root.right)
4. find maximum of left, right and return maximum of them + 1.

Code implementation below:

• Java

public class MaximumDepth {

    public static class Node {

        int val;

        Node left, right;

        // Constructor

        Node(int val) {

            this.val = val;

            left = right = null;

        }

    }

    public static void main(String[] args) {

        /*

         * Creating Binary Tree The created binary tree is same as in the above given

         * figure (refer figure for reference)

         */

        Node root = new Node(2);

        root.left = new Node(5);

        root.right = new Node(10);

        root.right.left = new Node(20);

        root.right.right = new Node(30);

        /*

         * calling findHeight(root) method and storing the value returned from this

         * method in height variable

         */

        int height = findHeight(root);

        System.out.println("Height of Binary Tree is: " + height);

    }

    public static int findHeight(Node root) {

        // if root is null i.e empty tree

        if (root == null)

            return 0;

        // calculating the leftSubTree height and storing the height

        int leftSubTree = findHeight(root.left);

        // calculating the rightSubTree height and storing the height

        int rightSubTree = findHeight(root.right);

        /*

         * returning maximum height from leftSubTree, rightSubTree adding 1 1 is added

         * for node height as per definition of height/maximum depth of binary tree

         */

        return Math.max(leftSubTree, rightSubTree) + 1;

    }

}

Output:

Height of Binary Tree is: 3

Complexity Analysis:

Time Complexity: O(n), as we have traversed each node of tree once. (n is number of nodes).
Space Complexity: O(1), we have not used any extra space for storing nodes.