Return the maximum number of edges from a binary tree's root to a leaf. The lesson counts edges: a singleton root has depth 0, its child has depth 1, and an empty tree returns -1. This convention differs from examples that count nodes or levels. Agree on it before writing the base case.
Store a depth beside each pending node
The selected implementation uses an explicit stack of node-and-depth pairs. Initialize it with the root at depth zero and initialize the maximum to -1. Pop a pair. If its node exists, update the maximum and push its children with depth increased by one. Null nodes contribute no depth and require no further expansion.
The stack makes the traversal depth first. Pushing right before left causes the left subtree to be visited first in versions that pop from the end, but visitation order does not affect the maximum. Every real node carries the depth calculated from the path used to reach it.
Trace an uneven tree
Suppose the root has a left leaf and a right child with its own right child. The root enters at depth 0. Its left leaf contributes 1. The right child also contributes 1, then its child contributes 2. The stored maximum ends at 2, regardless of which side is processed first.
A node with only one child still extends a path. Treating missing children as depth zero inside an edge-counting recurrence can miscount the empty tree or add an unwanted level. The explicit stack avoids that ambiguity by attaching the correct depth to real nodes and ignoring nulls.
Explain why every candidate is considered
Before each iteration, every unvisited real node is reachable through one of the pending subtree roots. Processing a real node records its depth and adds both child subtrees. Processing null discards an empty subtree. Thus no reachable node is omitted, and no real node is visited twice in an ordinary tree.
The maximum never decreases. After traversal it equals the greatest depth among all real nodes, which is the longest root-to-node path and therefore the longest root-to-leaf path. An internal node cannot exceed every descendant's depth, so considering all nodes instead of only leaves still returns the same answer.
Separate traversal storage from tree shape
Time is O(n), since every node and a bounded number of null child entries are processed. A depth-first stack holds pending siblings along the active path, using O(h) auxiliary space in the usual bound. A balanced tree has O(log n) height, while a skewed tree has O(n) height. The explicit stack avoids recursive call frames but still requires memory for its pending work.
A breadth-first version counts completed levels and can require O(w) queue storage for maximum width w. Neither traversal is universally smaller: a broad tree and a narrow chain stress different structures. A recursive solution is concise but must use an empty-subtree base of -1 to preserve this lesson's edge convention.
Test the convention and traversal
Test an empty tree for -1, a root alone for 0, one left child, one right child, a balanced tree, and a long chain. Put the deepest leaf in each side in separate cases. Trees with repeated data values are valid because this problem depends on structure, not search ordering or uniqueness.
For an independent check, run a breadth-first level traversal and subtract one from the number of nonempty levels, returning -1 when there are none. A follow-up can ask for the actual deepest path rather than its length. That requires retaining parent information or a path, since the numeric maximum alone cannot reconstruct which nodes formed the answer.
Rust implementation
The stack stores optional shared tree handles and depths. Cloning child Rc handles shares existing nodes; it does not clone entire subtrees.
The course supplies any declared node types and invokes the entry in impl Solution, or the design constructor shown here. Owned values move unless borrowed or cloned; the signature makes that choice explicit. An Option separates a missing node or result from a valid value. The runner enables integer overflow checks, so wider constraints require deliberate type and arithmetic changes.
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
pub fn find_max_depth(root: Option<Rc<RefCell<BinaryNode>>>) -> i32 {
let mut stack = Vec::new();
let mut max_depth = -1; // Value to return if no node is given
if root.is_some() {
// Updates to the correct root depth of 0
max_depth += 1;
// Add the root to the stack
stack.push((root, max_depth));
}
// Remove the top item on the stack and extract the node and its depth
while let Some((node, depth)) = stack.pop() {
// If the node exists, compare it to the current max and add its children to the stack
if let Some(node) = node {
let node = node.borrow();
max_depth = max_depth.max(depth);
stack.push((node.right.clone(), depth + 1));
stack.push((node.left.clone(), depth + 1));
}
}
max_depth
}
}
Practice this implementation
Open Binary Tree Max Depth to run the implementation against the course tests, then change one boundary condition and explain the first failing case. The editor supplies the starter signature and any node types or helper APIs used above. Copy the implementation into that environment; the snippet is the solution body, without the input parser or test driver. Your saved progress belongs to the original lesson.
For more Rust conventions and practice problems, use the Rust interview guide.