Maximum Depth of Binary Tree

The depth of a tree is 1 + the maximum depth of its left and right subtrees. This leads to a clean one-line recursive solution.

Algorithm:

• Base case: if root == null, depth is 0.
• Recursively compute depth of left and right subtrees.
• Return 1 + Math.max(leftDepth, rightDepth).

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    int leftDepth  = maxDepth(root.left);
    int rightDepth = maxDepth(root.right);
    return 1 + Math.max(leftDepth, rightDepth);
}

Complexity:

• Time: O(n). Visits every node once.
• Space: O(h). Recursion stack depth equals tree height (O(log n) balanced, O(n) worst).

Process the tree level by level with a queue. Each iteration of the outer loop represents one complete level: count the levels.

public int maxDepth(TreeNode root) {
    if (root == null) return 0;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int depth = 0;

    while (!queue.isEmpty()) {
        int levelSize = queue.size(); // nodes at current level
        depth++;
        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 depth;
}

Complexity:

• Time: O(n). Every node is enqueued and dequeued exactly once.
• Space: O(n). At most n/2 nodes in the queue at the widest level.