DSA-077 · Tree depth with explicit DFS state

Maximum Depth of Binary Tree

Foundation · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 1005 deterministic checks. Learner drafts are not executed.

Understand the problem

Return the number of nodes on a longest root-to-leaf path in a binary tree. An empty tree has depth zero.

Input is null or a finite proper binary tree with at most 100,000 nodes; no cycles or shared child objects. Node values may be any int.
Count nodes, not edges. A single node has depth 1; a null tree has depth 0. Preserve all node values, references, and child links.
The optimized implementation must handle deep skewed trees without Java recursive-stack overflow. Compact level-order arrays are used only in examples and test adapters; the method accepts Node.

Examples

Input: [3,9,20,null,null,15,7] in compact level order
Output: 3
The paths through node 20 to 15 or 7 contain three nodes.
Input: [1,null,2,null,3] in compact level order
Output: 3
A skewed tree is still depth three; breadth and depth are different measures.

Before you start

Binary tree references and finite acyclic structure
Depth counted in nodes and explicit versus call stacks

Recognize the structure

Depth is an accumulated path property. Either combine child heights recursively or carry a depth with each explicit traversal entry. A graph with shared nodes or cycles requires a different contract and visited/path reasoning.

Try before revealing

Hint 1

What should null and a leaf return?

Hint 2

An explicit traversal needs to remember each node’s depth.

Hint 3

Start root at one, propagate depth+1, and retain the greatest visited depth.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Combine child heights recursively

For null return 0; otherwise return 1+max(leftDepth,rightDepth). For a leaf, both child results are zero, giving one; its parent adds another. This visits every node once and uses O(h) call-stack space. It is algorithmically optimal in work, but a 100,000-node chain can overflow Java’s call stack, so it is limited to shallow validation cases.

Improve the baseline

Move suspended work into explicit frames

Use a stack of (node,depth) records, initially (root,1). This avoids dependence on recursive-stack depth.

Update the greatest visited depth

Pop a frame, compare its depth with best, and push non-null children with depth+1. The reference pushes right then left, so left is visited first.

Handle empty input separately

Return 0 before pushing null. ArrayDeque does not accept null, and the method does not invent a sentinel node.

Why it is correct

Initialize

For nonempty input, the root frame has its correct depth one. best=0 is the maximum over the empty visited set.

Preserve

Every pushed child has depth equal to its parent’s correct depth plus one. Since this is a proper tree, each node is reached exactly once. After each pop, best is the largest depth among visited nodes.

Finish

A finite tree yields a finite number of frames. Once the stack is empty all nodes were visited; the greatest node depth equals the length of a longest root-to-leaf path.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.ArrayDeque;
import java.util.Deque;

public final class Solution {
    public static final class Node {
        public final int value;
        public Node left, right;
        public Node(int value) { this.value = value; }
    }
    private record Frame(Node node, int depth) {}

    public static int maxDepth(Node root) {
        if (root == null) return 0;
        Deque<Frame> stack = new ArrayDeque<>();
        stack.push(new Frame(root, 1));
        int best = 0;
        while (!stack.isEmpty()) {
            Frame frame = stack.pop();
            best = Math.max(best, frame.depth());
            if (frame.node().right != null) stack.push(new Frame(frame.node().right, frame.depth() + 1));
            if (frame.node().left != null) stack.push(new Frame(frame.node().left, frame.depth() + 1));
        }
        return best;
    }

    public static int baseline(Node root) {
        if (root == null) return 0;
        return 1 + Math.max(baseline(root.left), baseline(root.right));
    }
}

Read the meaningful blocks

Define a complete Node type

The reference includes value, left, right, and constructor; no external tree class is assumed.

Keep depth in Frame

Stack size is not depth: a traversal may hold pending siblings from several ancestors.

Push only non-null children

Depth propagation and null checks preserve the frame invariant.

Complexity

Both algorithms take O(n) time. The explicit DFS stack uses O(h) auxiliary frames in the worst case (O(n) for height n), though a single-child chain itself holds only one pending frame at a time. Output is one int.

The baseline uses O(h) recursive call frames and risks stack overflow. A level-order alternative uses O(w) queue storage for maximum width w. No method here modifies the tree.

Exact-state walkthroughs

Reveal normal and boundary traces

Explicit depth frames

Input: [3,9,20,null,null,15,7] · Result: 3

Step 1 of 7: Attach depth one to a nonempty root.

Every pending frame carries its actual node depth.

Original tree identities and child links

n0: 3left → n1right → n2
n1: 9left → nullright → null
n2: 20left → n5right → n6
n5: 15left → nullright → null
n6: 7left → nullright → null

Node cards remain in identity order. The highlighted frame is being visited; its depth is in the state table.

State after this step
Variable	Value
treeNodes	`[{"id":"n0","value":3,"left":"n1","right":"n2"},{"id":"n1","value":9,"left":null,"right":null},{"id":"n2","value":20,"left":"n5","right":"n6"},{"id":"n5","value":15,"left":null,"right":null},{"id":"n6","value":7,"left":null,"right":null}]`
stack	`[{"id":"n0","depth":1}]`
visited	`[]`
best	`0`

See the affected Java block

 1 import java.util.ArrayDeque;
 2 import java.util.Deque;
 3 
 4 public final class Solution {
 5     public static final class Node {
 6         public final int value;
 7         public Node left, right;
 8         public Node(int value) { this.value = value; }
 9     }
10     private record Frame(Node node, int depth) {}
11 
12     public static int maxDepth(Node root) {
13         if (root == null) return 0;
14         Deque<Frame> stack = new ArrayDeque<>();
15         stack.push(new Frame(root, 1));
16         int best = 0;
17         while (!stack.isEmpty()) {
18             Frame frame = stack.pop();
19             best = Math.max(best, frame.depth());
20             if (frame.node().right != null) stack.push(new Frame(frame.node().right, frame.depth() + 1));
21             if (frame.node().left != null) stack.push(new Frame(frame.node().left, frame.depth() + 1));
22         }
23         return best;
24     }
25 
26     public static int baseline(Node root) {
27         if (root == null) return 0;
28         return 1 + Math.max(baseline(root.left), baseline(root.right));
29     }
30 }
31

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Attach depth one to a nonempty root.
Every pending frame carries its actual node depth.
treeNodes
[{"id":"n0","value":3,"left":"n1","right":"n2"},{"id":"n1","value":9,"left":null,"right":null},{"id":"n2","value":20,"left":"n5","right":"n6"},{"id":"n5","value":15,"left":null,"right":null},{"id":"n6","value":7,"left":null,"right":null}]
stack
[{"id":"n0","depth":1}]
visited
[]
best
0
Visit a node and push non-null children with depth+1.
best is the maximum visited depth; stack is displayed bottom to top.
frame
{"id":"n0","depth":1}
stack
[{"id":"n2","depth":2},{"id":"n1","depth":2}]
visited
["n0"]
best
1
Visit a node and push non-null children with depth+1.
best is the maximum visited depth; stack is displayed bottom to top.
frame
{"id":"n1","depth":2}
stack
[{"id":"n2","depth":2}]
visited
["n0","n1"]
best
2
Visit a node and push non-null children with depth+1.
best is the maximum visited depth; stack is displayed bottom to top.
frame
{"id":"n2","depth":2}
stack
[{"id":"n6","depth":3},{"id":"n5","depth":3}]
visited
["n0","n1","n2"]
best
2
Visit a node and push non-null children with depth+1.
best is the maximum visited depth; stack is displayed bottom to top.
frame
{"id":"n5","depth":3}
stack
[{"id":"n6","depth":3}]
visited
["n0","n1","n2","n5"]
best
3
Visit a node and push non-null children with depth+1.
best is the maximum visited depth; stack is displayed bottom to top.
frame
{"id":"n6","depth":3}
stack
[]
visited
["n0","n1","n2","n5","n6"]
best
3
Return the contract result.
The final state satisfies the requested output contract.
result
3

Empty tree

Input: [] · Result: 0

Step 1 of 2: Attach depth one to a nonempty root.

Every pending frame carries its actual node depth.

Original tree identities and child links

Node cards remain in identity order. The highlighted frame is being visited; its depth is in the state table.

State after this step
Variable	Value
treeNodes	`[]`
stack	`[]`
visited	`[]`
best	`0`

See the affected Java block

 1 import java.util.ArrayDeque;
 2 import java.util.Deque;
 3 
 4 public final class Solution {
 5     public static final class Node {
 6         public final int value;
 7         public Node left, right;
 8         public Node(int value) { this.value = value; }
 9     }
10     private record Frame(Node node, int depth) {}
11 
12     public static int maxDepth(Node root) {
13         if (root == null) return 0;
14         Deque<Frame> stack = new ArrayDeque<>();
15         stack.push(new Frame(root, 1));
16         int best = 0;
17         while (!stack.isEmpty()) {
18             Frame frame = stack.pop();
19             best = Math.max(best, frame.depth());
20             if (frame.node().right != null) stack.push(new Frame(frame.node().right, frame.depth() + 1));
21             if (frame.node().left != null) stack.push(new Frame(frame.node().left, frame.depth() + 1));
22         }
23         return best;
24     }
25 
26     public static int baseline(Node root) {
27         if (root == null) return 0;
28         return 1 + Math.max(baseline(root.left), baseline(root.right));
29     }
30 }
31

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Attach depth one to a nonempty root.
Every pending frame carries its actual node depth.
treeNodes
[]
stack
[]
visited
[]
best
0
Return the contract result.
The final state satisfies the requested output contract.
result
0

Test the contract

Input: null
Output: 0
Empty tree.
Input: [8]
Output: 1
One node.
Input: [1,2,3]
Output: 2
Balanced shallow tree.
Input: [1,2,null,3]
Output: 3
One-sided path.

Common mistakes and counterexamples

Return edge count

Counterexample: A single node must return 1, not 0.

Define depth in nodes.

Use stack size as depth

Counterexample: A root with one leaf may keep only one pending frame, but its depth is two.

Carry a depth in every frame.

Ignore recursive depth limits

Counterexample: A chain of 100,000 nodes may exhaust Java’s call stack.

Use explicit frames for the declared full input range.

Follow-ups

Return a deepest path.

Retain parent information or explicit path frames; reconstruct from a deepest leaf. Avoid copying a whole path per node unless its additional cost is intended.

Return minimum root-to-leaf depth.

A missing child is not a zero-length leaf path. BFS can stop at its first leaf; adjust the recurrence carefully for single-child nodes.

Compute diameter.

Combine the two greatest downward child heights at each node. A maximum root depth alone misses a path that crosses between two subtrees.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 89/20,000 characters

Self-review

I count nodes rather than edges.I propagate depth independently of stack size.I preserve structure and handle deep input iteratively.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Tree foundations: structure, depth, and traversal state

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-14 · Original explanations, examples, and Java implementations for AceYourInterviews. Familiar task names identify standard algorithmic problems; no company-frequency claims are made.