Binary tree maximum depth in Java: count edges

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.

Java implementation

A NodeAtDepth record carries a nullable node inside a non-null queue element. This avoids inserting null directly into ArrayDeque.

The course runner supplies standard java.util imports and calls the public methods on the class shown here. Keep helper methods inside that class. Java arrays and node objects are references, so changing an element or field can change the caller's data. The int arithmetic in the implementation is bounded; widen intermediate expressions when adapting it beyond the lesson constraints.

class Solution {
    // A node on the stack, along with its depth
    private record NodeAtDepth(BinaryNode node, int depth) {}

    public int findMaxDepth(BinaryNode root) {
        Deque<NodeAtDepth> stack = new ArrayDeque<>();
        int maxDepth = -1; // Value to return if no node is given

        if (root != null) {
            // Updates to the correct root depth of 0
            maxDepth = maxDepth + 1;
            // Add the root to the stack
            stack.push(new NodeAtDepth(root, maxDepth));
        }

        while (!stack.isEmpty()) {
            // Remove top item on the stack and extract the node and its depth
            NodeAtDepth top = stack.pop();
            BinaryNode node = top.node();
            int depth = top.depth();

            // If the node exists, compare it to the current max and add its children to the stack
            if (node != null) {
                maxDepth = Math.max(maxDepth, depth);
                stack.push(new NodeAtDepth(node.right, depth + 1));
                stack.push(new NodeAtDepth(node.left, depth + 1));
            }
        }

        return maxDepth;
    }
}

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 Java conventions and practice problems, use the Java interview guide.