Is the depth counted in nodes or in edges?

Nodes: a single node has depth 1 and None has depth 0, so [4, 2, 7, null, null, 6, 9, 5] gives 4. A height counted in edges is one less for every non-empty tree and -1 for the empty one; return -1 from the None arm to get it.

Why a helper that takes a reference instead of recursing on max_depth itself?

max_depth takes the tree by value, so calling it on a child means passing node.left.clone(): cloning an Option > is cheap, one reference-count increment and later a decrement, but it happens for every node. The helper takes &Option >>, and &node.left borrows the child through the Ref guard instead. Both are correct; the reference version simply does no counting at all.

Why does for _ in 0..queue.len() stop at the end of the level?

The range 0..queue.len() is evaluated once, when the for loop starts, into a Range value that no longer looks at the deque. Children pushed during the loop do not extend it, so it pops exactly the nodes that formed the current level. The borrow checker also allows this, because queue.len() has finished borrowing the deque before the body mutates it.

What happens if the recursion goes too deep?

Rust does not raise a catchable panic: the main thread's stack, usually 8 MB, hits its guard page and the process aborts with thread 'main' has overflowed its stack. A debug build uses more stack per frame than a release build, so it fails sooner. The cases here stay within 500 levels, far below that; for input whose depth you do not control, the VecDeque loop keeps its work on the heap.

How do I get the minimum depth instead?

Not by changing .max(...) to .min(...): a node with one child is not a leaf, and on [10, null, 20, null, 30] that returns 1 (the missing left child counts as a path of zero) instead of 3. Match on both children: when one is None, return one plus the other side's depth. In the queue loop, return depth at the first node whose left and right are both None.

Maximum Depth of a Binary Tree in Rust: Recursive and BFS Solutions

max_depth.rs

Rust 1.98

Not run yet

+ 7 hidden

Input

root = [4, 2, 7, null, null, 6, 9, 5]

Expected

The longest path is 4 → 7 → 6 → 5, four nodes. The branch through 2 ends after two, and 9 after three.

1 · Recursive DFS: one more than the deeper subtree

2 · Iterative BFS: count the levels with a queue

1 · Recursive DFS: one more than the deeper subtree

2 · Iterative BFS: count the levels with a queue

1 · Recursive DFS: one more than the deeper subtree

2 · Iterative BFS: count the levels with a queue

1 · Recursive DFS: one more than the deeper subtree

2 · Iterative BFS: count the levels with a queue

1 · Recursive DFS: one more than the deeper subtree

2 · Iterative BFS: count the levels with a queue

1 · Recursive DFS: one more than the deeper subtree

2 · Iterative BFS: count the levels with a queue

1 · Recursive DFS: one more than the deeper subtree

2 · Iterative BFS: count the levels with a queue

1 · Recursive DFS: one more than the deeper subtree

2 · Iterative BFS: count the levels with a queue

1 · Recursive DFS: one more than the deeper subtree

2 · Iterative BFS: count the levels with a queue

1 · Recursive DFS: one more than the deeper subtree

2 · Iterative BFS: count the levels with a queue

1 · Recursive DFS: one more than the deeper subtree

2 · Iterative BFS: count the levels with a queue

1 · Recursive DFS: one more than the deeper subtree

2 · Iterative BFS: count the levels with a queue

1 · Recursive DFS: one more than the deeper subtree

2 · Iterative BFS: count the levels with a queue

1 · Recursive DFS: one more than the deeper subtree

2 · Iterative BFS: count the levels with a queue

1 · Recursive DFS: one more than the deeper subtree

2 · Iterative BFS: count the levels with a queue