Height of a tree

Problem Statement

Given a binary tree, find its height (or maximum depth). The height of a tree is the number of edges on the longest path from the root to a leaf node.

Example:

• Input: Root of the above tree
• Output: 2 (edges) or 3 (nodes on longest path)

Note: Some definitions count nodes, others count edges. We'll use node count here.

Approach 1: Brute Force (BFS - Level by Level)

Intuition

Use level order traversal and count the number of levels. Each level adds 1 to the height.

Algorithm

1. Use a queue for BFS
2. For each level, increment height counter
3. Return the total count of levels

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public int heightBFS(TreeNode root) {
        if (root == null) return 0;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int height = 0;
        
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            height++;
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        
        return height;
    }
}

Complexity Analysis

• Time Complexity: O(n) - Visit each node once
• Space Complexity: O(n) - Queue can hold up to n/2 nodes (last level)

Approach 2: Optimal (DFS - Recursion)

Intuition

The height of a tree is 1 + maximum of heights of left and right subtrees. Use recursion to compute this elegantly.

Algorithm

1. Base case: if node is null, return 0
2. Recursively find height of left subtree
3. Recursively find height of right subtree
4. Return 1 + max(leftHeight, rightHeight)

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        
        return 1 + Math.max(leftHeight, rightHeight);
    }
}

Complexity Analysis

• Time Complexity: O(n) - Visit each node exactly once
• Space Complexity: O(h) - Recursion stack depth equals tree height, O(log n) for balanced tree, O(n) for skewed tree

Key Takeaways

1. Recursive formula: height = 1 + max(left_height, right_height)
2. The recursive DFS approach is cleaner and uses less space for balanced trees
3. BFS approach is useful when you want to avoid recursion or stack overflow
4. Height is a fundamental property used in many tree algorithms (balancing, diameter, etc.)
5. Be clear about whether you're counting edges or nodes