easy Maximum Depth or Height of Binary Tree

Problem Statement

Given a root node of the binary tree, return the depth (or height) of a binary tree.

The Depth of the binary tree refers to the number of nodes along the longest path from the root node to the farthest leaf node. If the tree is empty, the depth is 0.

Examples

Example 1

Input: root = [1, 2, 3, 4, 5]

Expected Output: 3
Explanation: The longest path is 1->2->4 or 1->2->5 with 3 nodes.

Example 2

Input: root = [1, null, 2, null, 3]

Expected Output: 3
Justification: There's only one path 1->2->3 with 3 nodes.

Example 3

Input: root = [1, 2, 3, 4, 7, null, null, null, null, null, 9]

Expected Output: 4
Justification: The longest path is 1->2->7->9 with 4 nodes.

Constraints:

The number of nodes in the tree is in the range [0, 10⁴].
-100 <= Node.val <= 100

Try it yourself

Try solving this question here:

🎯 STRICT STANDOUT — Maximum Depth / Height of Binary Tree — problem

1. Why / judgment

Depth here = number of nodes on longest root-to-leaf path (LeetCode convention). Empty tree → 0. Recurrence: depth(null)=0, depth(u)=1+max(depth(L),depth(R)). BFS level-count is equivalent. This is the gateway tree recursion problem — if this recurrence is shaky, diameter / balanced / leaves layers will fail.

2. Big-O derivation (K11)

DFS visits each node once: Θ(n) time.
Stack space Θ(h) worst Θ(n) skewed; Θ(log n) balanced.
BFS queue Θ(w) width.

3. Pattern + when-NOT (K12)

Name: TREE DFS HEIGHT RECURRENCE / BFS LEVELS

Recognition: “height/depth of binary tree”, longest root-leaf.

When-NOT: Need edge-count depth (some texts height = edges) → off-by-one; align definition. Need diameter (longest any-to-any) → extra state per node, not plain height alone. Need min depth → BFS first leaf better than full DFS.

4. Edge hand-run (K13)

null → 0.
single node → 1.
right spine length k → k.
perfect tree height h → h.

5. Interviewer follow-ups (model answers)

Q1. Height vs depth terminology?
A: Texts differ (edges vs nodes). Lock the problem statement: LC maxDepth counts nodes.

Q2. Why not store global only without return?
A: You can pass depth down; returning bottom-up max is cleaner for composition.

Q3. Balanced guarantee?
A: No — always budget O(n) stack.

6. Short drills

Drill: [1,2,3,4,5] → 3.
Drill: convert recursive to iterative stack simulating postorder.

✅ Solution Maximum Depth or Height of Binary Tree

Problem Statement

Given a root node of the binary tree, return the depth (or height) of a binary tree.

The Depth of the binary tree refers to the number of nodes along the longest path from the root node to the farthest leaf node. If the tree is empty, the depth is 0.

Examples

Example 1

Input: root = [1, 2, 3, 4, 5]

Expected Output: 3
Explanation: The longest path is 1->2->4 or 1->2->5 with 3 nodes.

Example 2

Input: root = [1, null, 2, null, 3]

Expected Output: 3
Justification: There's only one path 1->2->3 with 3 nodes.

Example 3

Input: root = [1, 2, 3, 4, 7, null, null, null, null, null, 9]

Expected Output: 4
Justification: The longest path is 1->2->7->9 with 4 nodes.

Constraints:

The number of nodes in the tree is in the range [0, 10⁴].
-100 <= Node.val <= 100

Solution

What's the 'Depth'?

Picture a ladder. Each step is a level in our tree. The depth? It's just how many steps there are! If we have a 3-step ladder, our tree has a depth of 3.

To determine the deepest level of a binary tree, we'll use a depth-first search (DFS) approach. Begin at the root node and traverse down each branch, keeping track of the current depth. The depth increases by one each time we move to a child node. If a node is a leaf (no children), compare its depth with the current maximum depth and update if necessary. Recursively apply this process to each node's left and right children. This will cover all paths in the tree, allowing us to find and return the maximum depth encountered.

Step-by-step Algorithm

Recursive Approach: The depth of a binary tree can be computed recursively. The maximum depth of a tree is the maximum of the depths of its left and right subtrees plus one (the root node).
Base Condition: If the node is null, return 0. This ensures that we've reached the end of a branch or the tree is empty.
Recursive Calculation: For each node, compute the depth of its left subtree and the depth of its right subtree. The depth of the current node is 1 + the maximum of these two depths.
Result: For the root node, this recursive approach will provide the maximum depth of the entire tree.

Algorithm Walkthrough

Starting at the root node 1:
- The method maxDepth(root) is called with the root node 1.
- The root node is not null, so we proceed to calculate the depth of its left and right subtrees.
Calculating the depth of the left subtree of node 1:
- The method maxDepth(root.left) is called with the left child of node 1, which is node 2.
Calculating the depth of the left subtree of node 2:
- The method maxDepth(root.left.left) is called with the left child of node 2, which is node 4.
- Node 4 is a leaf node (no left or right children).
- The method maxDepth(root.left.left.left) is called with null (left child of 4), returning 0.
- The method maxDepth(root.left.left.right) is called with null (right child of 4), returning 0.
- The maximum depth from node 4 is 1 + max(0, 0) = 1.
Calculating the depth of the right subtree of node 2:
- The method maxDepth(root.left.right) is called with the right child of node 2, which is node 5.
- Node 5 is a leaf node (no left or right children).
- The maximum depth from node 5 is 1 + max(0, 0) = 1.
Determining the depth of node 2:
- Node 2 has a left depth of 1 (from node 4) and a right depth of 1 (from node 5).
- The maximum depth from node 2 is 1 + max(1, 1) = 2.
Calculating the depth of the right subtree of node 1:
- The method maxDepth(root.right) is called with the right child of node 1, which is node 3.
- Node 3 is a leaf node (no left or right children).
- The maximum depth from node 3 is 1 + max(0, 0) = 1.
Determining the depth of the root node 1:
- Node 1 has a left depth of 2 (from node 2) and a right depth of 1 (from node 3).
- The maximum depth of the tree rooted at node 1 is 1 + max(2, 1) = 3.

Final Output: The maximum depth of the tree [1, 2, 3, 4, 5] is 3.

Code

Here is the code for this algorithm:

java

// Definition for a binary tree node.
// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode(int x) { val = x; }
// }

public class Solution {

  // Method to compute the maximum depth of a binary tree
  public int maxDepth(TreeNode root) {
    // Base case: if node is null, return 0
    if (root == null) return 0;

    // Recursively calculate left subtree depth
    int leftDepth = maxDepth(root.left);

    // Recursively calculate right subtree depth
    int rightDepth = maxDepth(root.right);

    // Return the maximum of left and right subtree depth plus 1 for the current node
    return Math.max(leftDepth, rightDepth) + 1;
  }

  public static void main(String[] args) {
    Solution solver = new Solution();

    // Example 1
    TreeNode root1 = new TreeNode(1);
    root1.left = new TreeNode(2);
    root1.right = new TreeNode(3);
    root1.left.left = new TreeNode(4);
    root1.left.right = new TreeNode(5);
    System.out.println(solver.maxDepth(root1)); // Expected output: 3

    // Example 2
    TreeNode root2 = new TreeNode(1);
    root2.right = new TreeNode(2);
    root2.right.right = new TreeNode(3);
    System.out.println(solver.maxDepth(root2)); // Expected output: 3

    // Example 3
    TreeNode root3 = new TreeNode(1);
    root3.left = new TreeNode(2);
    root3.right = new TreeNode(3);
    root3.left.left = new TreeNode(4);
    root3.left.right = new TreeNode(7);
    root3.left.right.right = new TreeNode(9);
    System.out.println(solver.maxDepth(root3)); // Expected output: 4
  }
}

Complexity Analysis

Time Complexity

Recursive Calls:
- The algorithm uses recursion to traverse each node in the binary tree exactly once. For each node, it makes a recursive call for the left child and the right child.
- If the binary tree has n nodes, there will be n recursive calls in total.
- Therefore, the time complexity for traversing the entire tree is .
Calculating Maximum Depth:
- For each node, the algorithm calculates the maximum of the left and right subtree depths, which is a constant time operation .

Combining these steps, the overall time complexity of the algorithm is .

Space Complexity

Recursive Stack Space:
- The depth of the recursion stack is determined by the height of the tree. In the worst case, if the tree is skewed (i.e., all nodes are in a single line), the height of the tree will be n, resulting in a space complexity of for the recursion stack.
- In the best case (a balanced tree), the height of the tree will be , resulting in a space complexity of .
Additional Space:
- The algorithm does not use any additional space other than the recursion stack.

🎯 STRICT STANDOUT — Solution Maximum Depth or Height of Binary Tree

1. Why / judgment

Post-order: know both children depths before deciding. Base null→0 prevents NPE and gives leaf depth 1. Equivalent BFS: increment answer each level until queue drains.

2. Big-O derivation (K11)

T(n)=T(nL)+T(nR)+Θ(1) ⇒ Θ(n).
Space Θ(h).
Trace [1,2,3,4,5]: leaves 4,5 depth from root path length 3; right leaf 3 path length 2 → answer 3.
Trace [1,null,2,null,3] → 3.

3. Pattern + when-NOT (K12)

Name: POSTORDER HEIGHT

Recognition: binary tree max depth.

When-NOT: N-ary tree → max over all children. Graph with cycles → not a tree; need visited.

4. Edge hand-run (K13)

empty 0.
skewed left n nodes → n.
values irrelevant — structure only.

5. Interviewer follow-ups (model answers)

Q1. Can you DFS with running max without return values?
A: Yes: void dfs(node,d) update ans; d+1 to children. Same asymptotics.

Q2. Morris traversal?
A: Not helpful for height; stackless height needs different care.

Q3. Integer overflow on depth?
A: n≤1e4 typically; depth fits int.

6. Short drills

Drill: prove by induction on tree size.
Drill: BFS version counting levels.

🧩 Pattern · Trees

Recognize it: Hierarchical data → recurse on children; BFS (queue) for level-order, DFS (recursion) for paths.

▶ Visualize this problem (step it, predict each fork)

⛶ Open this problem debugger in explore mode

🤖 Don't fully get this? Learn it with Claude

Stuck on Maximum Depth or Height of Binary Tree? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Maximum Depth or Height of Binary Tree** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Maximum Depth or Height of Binary Tree** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Maximum Depth or Height of Binary Tree**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Maximum Depth or Height of Binary Tree**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Monotonic Array Missing Ranges →