☕ DSA Java Articles

Topics › Binary Trees › Medium Problems

Maximum Depth in BT

Medium TUF ID 131 A2ZSDEBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given the root of a binary tree, return its maximum depth: the number of nodes on the longest path from the root down to a leaf. An empty tree has depth 0 and a single node has depth 1. The same quantity is often called the height of the tree.

Constraints: 0 ≤ n ≤ 10^4 nodes in the LeetCode version, values fit in an int. The tree can be completely skewed, so the depth can be as large as n.

Example 1

tree (level order) = [3, 9, 20, null, null, 15, 7]

     3
    / \
   9   20
      /  \
     15   7

answer = 3          // 3 -> 20 -> 15 (or 3 -> 20 -> 7) has three nodes

Example 2

tree (level order) = [1, null, 2]

answer = 2          // 1 -> 2

A note on conventions: some textbooks count edges instead of nodes, which makes every answer one smaller and the empty tree -1. This article and the Java file count nodes, as LeetCode and the TUF sheet do.

Approach 1: Level-order traversal (BFS)

Intuition. The depth is the number of levels. A breadth-first traversal naturally processes a tree level by level: if, at the start of each round, we note how many nodes are in the queue, those nodes are exactly one level. Process them all (adding their children to the queue for the next round), and count the rounds.

Algorithm.

  1. If the root is null, return 0. Otherwise put the root in a queue and set depth = 0.
  2. While the queue is not empty:
    • Let size be the current queue size.
    • Poll size nodes, adding each one’s existing children to the queue.
    • Increase depth by one.
  3. Return depth.
static int levelOrder(TreeNode root) {
    if (root == null) return 0;
    Deque<TreeNode> q = new ArrayDeque<>();
    q.add(root);
    int depth = 0;
    while (!q.isEmpty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            if (node.left != null) q.add(node.left);
            if (node.right != null) q.add(node.right);
        }
        depth++;
    }
    return depth;
}

Complexity. Time O(n): each node enters and leaves the queue once. Space O(w), where w is the maximum number of nodes on one level. For a complete tree the last level holds about n / 2 nodes, so the queue can be large, but there is no recursion, so a skewed tree is harmless.

Approach 2: Recursion

Intuition. Think about the root alone. The longest root-to-leaf path goes down into either the left subtree or the right subtree, and inside that subtree it is again a longest root-to-leaf path. So the depth of a tree is one (for the root) plus the larger of the two subtree depths. The base case is the empty tree with depth 0. This is the cleanest formulation, and the pattern “ask both children, combine their answers, return one number to the parent” is the template for most of the tree problems that follow (balanced tree, diameter, maximum path sum).

Algorithm.

  1. If the node is null, return 0.
  2. Return 1 + max(depth(left), depth(right)).
static int recursive(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(recursive(root.left), recursive(root.right));
}

Dry run on Example 1. The calls return bottom-up:

node depth(left) depth(right) returns
9 0 0 1
15 0 0 1
7 0 0 1
20 1 1 2
3 1 2 3

Complexity. Time O(n): every node is visited exactly once and does constant work. Space O(h) for the call stack, where h is the depth itself: O(log n) for a balanced tree, O(n) for a skewed one.

Approach 3: Iterative DFS with an explicit stack

Intuition. Approach 2 is the one to write in an interview, but a skewed tree with 10^5 nodes can overflow the Java call stack. The fix is to carry the depth along with each node on an explicit stack. Whenever a node is popped, we know exactly how deep it is, so we keep a running maximum. Children are pushed with depth + 1. The order in which nodes are visited does not matter for a maximum, so any traversal order works.

Algorithm.

  1. If the root is null, return 0. Push (root, 1).
  2. While the stack is not empty: pop (node, d), update best = max(best, d), push each existing child with d + 1.
  3. Return best.
static int iterativeDfs(TreeNode root) {
    if (root == null) return 0;
    Deque<TreeNode> nodes = new ArrayDeque<>();
    Deque<Integer> depths = new ArrayDeque<>();
    nodes.push(root);
    depths.push(1);
    int best = 0;
    while (!nodes.isEmpty()) {
        TreeNode node = nodes.pop();
        int d = depths.pop();
        best = Math.max(best, d);
        if (node.left != null) { nodes.push(node.left); depths.push(d + 1); }
        if (node.right != null) { nodes.push(node.right); depths.push(d + 1); }
    }
    return best;
}

Two parallel stacks are used instead of a pair class to keep the code short; they are always pushed and popped together, so they stay in step.

Complexity. Time O(n). Space O(h): the stack holds at most the nodes along one path plus one pending sibling per level. The Java file checks this method and the BFS on a 100 000-node chain, where the recursive version would be risky.

Which one to use

All three are O(n) time, and there is no asymptotically faster method: any algorithm has to look at every node, because an unvisited node could be the top of a long chain. The choice is about space and readability:

Edge cases and pitfalls