Blind 75 Visualized

#29 · Trees

Maximum Depth of Binary Tree

Given the root of a binary tree, return its maximum depth: the number of nodes on the longest path from the root down to the farthest leaf.

EasyLeetCode
  • Current node
  • On the path / call stack
  • Done / found
  • Rejected
  • Temporary thread (Morris)
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Binary tree

Each node holds a value and up to two children. A tree is recursive by definition: the left and right children are themselves trees. That is why most tree questions have a one-line recursive answer.

Memory layout

Nodes are separate heap objects linked by pointers, with poor cache locality. A complete tree can be stored in an array (children of i at 2i+1 and 2i+2), but general trees cannot.

OperationCost
visit every node (any traversal)O(n)
depth-first extra spaceO(h): the call stack, h = height
breadth-first extra spaceO(w): the widest level

Recursion / call stack

depth(node) = 1 + max(depth(left), depth(right)), with depth(empty) = 0. The system call stack remembers where each unfinished ancestor stopped. An explicit stack does the same thing without the recursion limit.

Memory layout

One stack frame per ancestor on the current path: h frames. A skewed tree of 100,000 nodes means 100,000 frames, which can overflow.

OperationCost
recursion depthO(h): between log n and n

Why it fits

  • The answer for a node depends only on the answers of its two subtrees: a textbook post-order (children first) computation.
  • Every node must be examined once (any leaf could be the deepest), so O(n) time is optimal; the real choice is how much memory the traversal uses.
  • DFS memory is the height; BFS memory is the width. For a balanced tree the height is tiny (log n), for a skewed tree the width is tiny: pick accordingly.

Why alternatives degrade

Only walking the leftmost path:
The deepest leaf can be anywhere; a single path says nothing about the others.
Converting the tree to an array first:
An extra O(n) pass and memory just to run the same traversal.
Recursion on a degenerate (linked-list-shaped) tree:
Correct but the call stack grows to n frames and overflows for large n: use BFS, an explicit stack or Morris traversal.

Four approaches, from naive to production

1 · beginner

Recursive DFS

time O(n)space O(h)

The depth of an empty tree is 0; otherwise it is 1 plus the larger of the depths of the left and right subtrees.

int maxDepth(TreeNode* root) {
    if (!root) return 0;
    int left = maxDepth(root->left);
    int right = maxDepth(root->right);
    return 1 + max(left, right);
}

Flaws & bottlenecks

  • Uses one call-stack frame per level: O(n) on a skewed tree, which can overflow the stack for very deep trees.
  • The recursion hides the order of work, which makes the stack depth easy to overlook.
  • Visits empty children too (about n + 1 extra calls).

Interviewer cross-questions

What are the time and space complexities?

Say: Time O(n): every node is visited once. Space O(h) for the call stack, where h is the height: O(log n) if balanced and O(n) if the tree is a chain.

What happens for a tree with 10⁶ nodes in a chain?

Say: The recursion depth is 10⁶ frames, which overflows the stack in most runtimes. Use BFS, an explicit stack, or Morris traversal.

Is this pre-order or post-order?

Say: Post-order: the answer for a node is computed AFTER both children have returned.

2 · intermediate

BFS, count the levels

time O(n)space O(w)

Process the tree level by level with a queue. Each pass over the current level adds 1 to the depth.

int maxDepth(TreeNode* root) {
    if (!root) return 0;
    queue<TreeNode*> queue; queue.push(root);
    int depth = 0;
    while (!queue.empty()) {
        depth++;
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode* node = queue.front(); queue.pop();
            if (node->left) queue.push(node->left);
            if (node->right) queue.push(node->right);
        }
    }
    return depth;
}

Flaws & bottlenecks

  • The queue can hold up to half of all nodes (a full last level): O(n) space for bushy trees.
  • queue.shift() is O(n) in some runtimes (arrays), so a naive queue can make it O(n²); use an index or a deque.
  • More code than the recursive version for the same answer.

Interviewer cross-questions

Why capture size before the inner loop?

Say: The queue grows while we process the level. Fixing size first separates this level from the children being added for the next one.

When is BFS better than DFS here?

Say: For very deep, skinny trees: BFS memory is the width (small), DFS memory is the height (huge). It also needs no recursion, so no stack overflow.

How would you avoid the O(n) shift?

Say: Keep a head index into the array, or swap two arrays (current level, next level), or use a real deque.

3 · advanced

Iterative DFS with (node, depth) pairs

time O(n)space O(h)

Replace recursion with an explicit stack of (node, depth) pairs. Pop a node, record its depth, push its children with depth + 1.

int maxDepth(TreeNode* root) {
    if (!root) return 0;
    vector<pair<TreeNode*, int>> stack = {{root, 1}};
    int best = 0;
    while (!stack.empty()) {
        auto [node, depth] = stack.back(); stack.pop_back();
        best = max(best, depth);
        if (node->right) stack.push_back({node->right, depth + 1});
        if (node->left) stack.push_back({node->left, depth + 1});
    }
    return best;
}

Flaws & bottlenecks

  • Allocates a small tuple for every push.
  • Still O(h) memory: O(n) for a chain, though now on the heap, so it will not overflow the call stack.
  • Order of pushes (right then left) matters only if you care about the visiting order.

Interviewer cross-questions

Why is this safer than recursion?

Say: The stack lives on the heap and grows as needed, so a very deep tree cannot overflow the (small, fixed) call stack.

Why push the right child first?

Say: The stack is last-in first-out, so the left child is popped first and the traversal is a normal pre-order. For this problem the order does not affect the answer.

Can you do it with O(1) extra space?

Say: Yes, Morris traversal temporarily threads right pointers to climb back up without a stack. It restores the tree before returning.

4 · expert

Morris traversal (O(1) space)

time O(n)space O(1)

Walk the tree with no recursion and no stack. Before descending into a left subtree, make its rightmost node point back at the current node (a thread). Follow the thread to climb back, then remove it. Track depth by hand.

int maxDepth(TreeNode* root) {
    int best = 0;
    int depth = 1;
    TreeNode* cur = root;
    while (cur) {
        if (!cur->left) {
            best = max(best, depth);
            cur = cur->right;
            depth++;
        } else {
            TreeNode* pred = cur->left;
            int steps = 1;
            while (pred->right && pred->right != cur) {
                pred = pred->right;
                steps++;
            }
            if (!pred->right) {
                best = max(best, depth);
                pred->right = cur;
                cur = cur->left;
                depth++;
            } else {
                pred->right = nullptr;
                depth -= steps;
                cur = cur->right;
            }
        }
    }
    return best;
}

Flaws & bottlenecks

  • Temporarily mutates the tree, so it is unsafe if other threads read it, and an exception mid-walk would leave threads behind.
  • Each edge is walked about twice, so the constant is higher than a plain DFS.
  • Depth bookkeeping across threads is subtle: the pointer jump up the tree must be compensated manually (depth -= steps).

Interviewer cross-questions

Why does the thread give O(1) space?

Say: The thread is the "return address": it replaces the stack frame that would remember where to resume after the left subtree. The tree itself stores the information, then is restored.

Why subtract steps when climbing up?

Say: After the left subtree is done we arrive from the predecessor, which is steps levels below the node we are returning to. The depth we carry is that of the predecessor (plus one), so we subtract to get the depth of the node's right child.

When would you ship this?

Say: Rarely: only in memory-constrained environments with trees too deep for recursion and a single-threaded, exception-safe context. BFS or an explicit stack is simpler and nearly as cheap.

Synchronized code walkthrough

Showing: Recursive DFS — shares the player above; click any step to jump.

int maxDepth(TreeNode* root) {
    if (!root) return 0;
    int left = maxDepth(root->left);
    int right = maxDepth(root->right);
    return 1 + max(left, right);
}