How deep is the deepest branch?

Trees Junior Python 3.13+ Kotlin 2.4+ Reviewed By Best Latest Apps

Pick the fix

A chain-shaped tree of 5,000 nodes makes the recursive version crash in CPython. What is the best fix?

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A Walk it with a queue or an explicit stack instead

Right: the work stays O(n) and nothing depends on the call stack.

The default limit is 1000 frames, and an iterative walk removes that ceiling without changing the cost.

Why not the others?
  • B Raise the recursion limit to 10**9. That can crash the interpreter itself when the real C stack overflows.
  • C Memoise the depth function. Each node is visited once already; the problem is depth, not repeats.
The tree 8, 3, 10, 1, 6, 14, 4, 7 visited in pre-order; depth grows by one on each step down.

Steps come from running the Python solution.

Text version

preorder:

Tree:

  • 8
    • 3 (left)
      • 1 (left)
      • 6 (right)
        • 4 (left)
        • 7 (right)
    • 10 (right)
      • 14 (right)
  1. Visit 8
  2. Visit 3
  3. Visit 1
  4. Visit 6
  5. Visit 4
  6. Visit 7
  7. Visit 10
  8. Visit 14

Result: 4. Order: 8, 3, 1, 6, 4, 7, 10, 14

level order:

Tree:

  • 8
    • 3 (left)
      • 1 (left)
      • 6 (right)
        • 4 (left)
        • 7 (right)
    • 10 (right)
      • 14 (right)
  1. Visit 8
  2. Visit 3
  3. Visit 10
  4. Visit 1
  5. Visit 6
  6. Visit 14
  7. Visit 4
  8. Visit 7

Result: 4. Order: 8, 3, 10, 1, 6, 14, 4, 7

30-second answer

The depth of a tree is one more than the deeper of its two subtrees; an empty tree has depth 0. That recursion visits each node once: O(n) time, and O(h) stack for a tree of height h.

Practise saying it · 30 s. No recording, just a timer

Explain the depth recursion and its cost.

Say your answer out loud, then check which of these points you covered:

  • 1 + max(left, right)
  • O(n) time
  • O(h) stack

Deep dive

This is the template for 'combine the children's answers': base case, recurse left and right, combine.

BFS that counts layers also works and avoids deep recursion on chain-shaped trees.

Height is sometimes counted in edges rather than nodes; agree on which.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def depth(root: Node | None) -> int:
    if not root:
        return 0  # an empty branch adds nothing
    return 1 + max(depth(root.left), depth(root.right))

Kotlin Ran on Kotlin 2.4.21 · JDK 21.0.12.1
Kotlin 2.4
fun depth(root: Node?): Int {
    if (root == null) return 0
    return 1 + maxOf(depth(root.left), depth(root.right))
}

Common mistakes

  • Returning 1 for an empty tree.
  • Counting edges when the question counts nodes, or the reverse.

Senior take & follow-ups

Say the recursion in one sentence before writing it. For a question this short, clarity is the whole score.

Follow-up questions

Think of your answer first, then open the hint.

  1. What about the shallowest leaf?

    Show hint

    BFS and stop at the first leaf, or recurse but ignore missing children.

  2. How do you avoid recursion limits?

    Show hint

    Use an explicit stack of (node, depth) pairs or a level-by-level queue.

See it animated on iPhone (Binary Tree in DSA Master - Data & Algorithms)

What each operation costs: Binary Tree · Binary Search Tree · Tree Traversal

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.