Height of Binary Tree

Time: O(n)

Space: O(h)

Intuition

The height is the number of nodes on the longest path from root to a leaf. Recursively: height = 1 + max(height(left), height(right)). Base: null node has height 0.

Algorithm

1If node is null, return 0.
2Return 1 + max(Height(node.left), Height(node.right)).

Example Walkthrough

Input: Tree: 1â†’(2â†’4, 3)

1.Height(4)=1. Height(2)=2. Height(3)=1. Height(1)=3.

Output: 3

Common Pitfalls

•Height of a single node is 1 (not 0). Height of empty tree is 0.

Height of Binary Tree.java

Java

// Approach: DFS. Return 1 + max(height(left), height(right)). Base case: null node returns 0.
// Time: O(n) Space: O(h)
class Node {
    int data;
    Node left, right;

    Node(int item) {
        data = item;
        left = right = null;
    }
}

class Solution {
    // Function to find the height of a binary tree.
    int height(Node node) {
        if (node == null)
            return -1;
        return Math.max(height(node.left), height(node.right)) + 1;
    }
}

Was this solution helpful?