Height of Binary Tree Java | Fresher Interview

Direct Answer

The height of a binary tree is the number of edges (or nodes, by convention) on the longest path from the root to a leaf. Compute it recursively: a node's height is 1 + max(height(left), height(right)), with an empty subtree returning 0 (or -1 for edge-count). It's O(n) time and O(h) stack space - a clean post-order recursion.

Deep Dive & Architecture

Height is the length of the longest path from a node down to a leaf. Define the unit before coding: many questions count nodes, while others count edges.

For node-count height, an empty tree has height 0 and a leaf has height 1. The recurrence is:

height(node) = 1 + max(height(node.left), height(node.right))

Worked example

Suppose root 1 has children 2 and 3, and node 2 has child 4. Both node 4 and node 3 return 1. Node 2 receives left height 1 and right height 0, so it returns 2. Root 1 receives 2 and 1, then returns 3. The longest root-to-leaf path is 1 -> 2 -> 4.

This is post-order reasoning: the parent cannot know its height until both child calls return. If height is counted in edges, use null -> -1, so a leaf returns 0. Mixing an edge base case with a node-count explanation creates an off-by-one result.

Every node is evaluated once, so time is O(n). The recursive stack is O(h), which is O(log n) for a balanced tree and O(n) for a completely skewed tree.

Code Example

class Node { int val; Node left, right; Node(int v){ val = v; } }

int height(Node node) {
    if (node == null) return 0;                 // empty subtree (node count)
    int lh = height(node.left);
    int rh = height(node.right);
    return 1 + Math.max(lh, rh);                // root contributes 1
}

//        1
//       / \
//      2   3
//     /
//    4
// height(4)=1; height(2)=1+max(1,0)=2; height(3)=1; height(1)=1+max(2,1)=3

Common Mistakes & Pitfalls

• Inconsistent base case: node-count returns 0 for null; edge-count returns -1. Don't mix them.
• Top-down depth confusion: height is naturally bottom-up (post-order); don't conflate with root-down depth.
• Off-by-one: forgetting the 1 + for the current node.
• Deep/skewed trees: recursion is O(h) stack; a skewed tree (h=n) can risk stack overflow.