parikshan

maximum-depth-of-binary-tree

Difficulty: Easy  ·  Topic: Trees  ·  Practice it on parikshan: /practice/maximum-depth-of-binary-tree/start

The story

A backup tool at a cloud provider walks every customer's home directory once a night. Most directories are shallow, but a few are pathological: a developer who unzipped a tarball of node_modules produces a folder tree thousands of levels deep, with one file at the bottom. Before the tool decides how to parallelise the walk, it needs to know how deep the deepest branch actually goes. That single number drives the size of the worker pool, the recursion budget, the timeout, and the alert threshold for "this customer is doing something weird".

That is maximum-depth-of-binary-tree. The folders are nodes, the parent-child relationship is the tree, and "how deep" is the answer. Once you see this problem in this framing, you will spot it everywhere a system needs the worst-case length of a hierarchy: org charts, DOM trees, dependency graphs, comment threads, sitemap crawls.

What's actually being asked

Given a binary tree, return the maximum depth, defined as the number of nodes on the longest path from the root down to the farthest leaf. The empty tree has depth 0. A single node has depth 1.

The input is a level-order JSON array with null for missing children. The output is a single integer.

The naive approach

Walk every root-to-leaf path, record its length, take the maximum across all paths. That works, but it visits leaves redundantly: a balanced tree has n/2 leaves, so you end up listing exponentially many paths in the worst case. The naive answer is correct on small trees and useless on real ones.

A subtler trap: build all paths into a list, then take the max length. That allocates O(n) memory per path and O(n) paths. You will run out of memory before you run out of time.

The key insight

A tree is recursive by definition: it is either empty, or it is a root with a left subtree and a right subtree. The depth obeys the same shape. The depth of an empty tree is 0. The depth of any other tree is 1 + max(depth(left), depth(right)). That is one line of recurrence and the whole algorithm.

This is the cleanest example of the "return a value" recursion in the Trees primer. The function signature reads like an English sentence about a subtree: max_depth(node) returns the max depth of the subtree rooted at node. No globals, no side effects, no extra parameters.

Step-by-step approach

  1. Parse the level-order array into a tree of nodes with .left and .right pointers, treating null as a missing child.
  2. Define max_depth(node):
    • If node is None, return 0.
    • Otherwise return 1 + max(max_depth(node.left), max_depth(node.right)).
  3. Call max_depth(root) and print the result.

For production safety on a 10,000-node skewed input, swap the recursion for an explicit stack of (node, depth_so_far) pairs and track a running maximum. The algorithm is the same; only the execution mechanism changes.

Worked example

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

       3
      / \
     9   20
        /  \
       15   7
  • max_depth(15) = 1 + max(0, 0) = 1
  • max_depth(7) = 1 + max(0, 0) = 1
  • max_depth(9) = 1 + max(0, 0) = 1
  • max_depth(20) = 1 + max(1, 1) = 2
  • max_depth(3) = 1 + max(1, 2) = 3

Answer: 3. The longest path is 3 -> 20 -> 15 or 3 -> 20 -> 7, both three nodes.

Complexity

  • Time: O(n). Each node contributes one comparison, one addition, and at most two recursive calls.
  • Space: O(h) where h is the tree's height. That is O(log n) for a balanced tree, O(n) for a skewed one. The space is the recursion stack (or the explicit iterative stack).

There is no better complexity available: you must look at every node to know whether it extends the deepest path.

Common pitfalls

  • Off-by-one on depth vs. height: some sources define depth in edges (a single node has depth 0), others in nodes (a single node has depth 1). This problem uses nodes. Read the spec.
  • Recursing into None: writing max(max_depth(node.left), max_depth(node.right)) without first checking node is None causes an AttributeError on the empty tree. Guard the base case first.
  • Stack overflow on a chain: Python's default recursion limit is around 1000. A right-skewed tree of 10000 nodes will crash. The graders include exactly this shape. Use an iterative stack.
  • Forgetting the empty tree: [] must return 0, not crash. Test it first.

Where this shows up in the enterprise

  • File systems: du --max-depth, find -maxdepth, and tar's recursion all need to know how deep the tree goes before deciding to bail or parallelise. Apple's Time Machine and Dropbox both probe maximum depth before scheduling a sync.
  • DOM rendering: browsers compute the height of the DOM tree on every layout pass; very deep DOMs (often built by misbehaving React lists) trigger reflow stalls.
  • Database indexes: PostgreSQL and MySQL track the height of every B-tree index; a B-tree exceeding a critical depth triggers a rebalance.
  • MongoDB: each collection's WiredTiger storage engine maintains a B-tree per index; depth metrics are surfaced in db.collection.stats().
  • Compiler ASTs: TypeScript, Babel, and ESLint compute AST depth to decide between recursive and iterative visitors. The TypeScript compiler explicitly checks AST depth before recursing further.
  • CDN routing tables: Cloudflare and Fastly build prefix trees from BGP announcements; the depth of the longest match determines the worst-case lookup cost per packet.
  • Comment threads: Reddit, Hacker News, and Disqus all clip threads beyond a maximum depth to keep the layout sane and the queries bounded.
  • Game-state search: chess engines such as Stockfish track the deepest line examined; "depth 24" is the public metric for a typical move.

The pattern is universal: any time a hierarchy can grow unboundedly, somebody needs the worst-case depth before scheduling work against it.

Variants you'll see elsewhere

  • minimum-depth-of-binary-tree: same recursion, replace max with min, but with a subtle leaf-only case (an internal node with one empty child cannot count the empty child).
  • count-nodes: replace max with + and the base case 0 is reused.
  • sum-of-subtree-values: same recursion, different combine step.
  • is-balanced: combines depth with a balance flag, the canonical "return a tuple" upgrade.
  • diameter: the next problem you will hit, where the recursion returns depth but also updates a global.

Every "summarise the subtree in a single number" problem starts here.

How parikshan turns this into a learning loop

After you read this article and click through to the practice link, the parikshan flow integrates four layers:

  1. The editor runs your code against public tests for instant feedback, and against per-session dynamic private tests (generated freshly per session) so memorising someone else's solution is useless. The depth tests include a left-skewed chain of 800 nodes that will crash a naive recursive solution; you have to learn the iterative form to clear them.
  2. Hints are graduated. Take the first hint and you sacrifice a few integrity points for one line of nudge ("what does depth mean for a leaf?"). Take the third hint and you get the full algorithmic skeleton, at a larger penalty. The integrity score is the platform's measure of independent thinking.
  3. The AI training assistant is a sparring partner, not an answer key. In exam mode, you can ask it to Explain the problem, Review your current code, Find Bugs, Add Comments, or Optimise. Each request docks integrity by a small amount, so the cost forces you to choose deliberately. In practice mode, AI chat is free-form and free of penalty.
  4. The dispute flow runs after the verdict. If you believe your solution is correct and the judge is wrong, one click sends the code to a human reviewer. The reviewer can override the verdict.

Read the concept, attempt the problem in practice mode first, accept the integrity hit only when you genuinely need a hint, then redo the problem in exam mode with no help. When you can solve it in exam mode in under four minutes without touching AI, the pattern is in your fingers.

In the AI-integrated workspace

In your future job, you will not write max_depth from scratch. An agent will. Your job is to:

  1. Recognise that "how deep is this hierarchy" is a max-depth question, and that any recursive descent will visit every node exactly once.
  2. Tell the agent precisely: "use the recurrence 1 + max(depth(left), depth(right)), and use an explicit stack so it survives a 10,000-node skewed input".
  3. Read the agent's code and verify the base case for the empty tree comes before any attribute access.
  4. Stress-test on the edge cases the agent will silently miss: the empty tree, a single node, a left-only chain, a right-only chain.

Candidates who can name "this is max-depth" within five seconds of reading the spec are the ones who direct AI agents productively. Candidates who cannot recognise the pattern end up reading 30 lines of generated path-enumeration code and approving it because the sample passes. parikshan is built to train the first kind.