# The Tree Measurer

> How deep does the rabbit hole go?

Canonical URL: <https://datadriven.io/problems/the_tree_measurer>

Domain: Python · Difficulty: easy · Seniority: L3

## Problem

Given the root of a binary tree (nested dict with 'val', 'left', 'right'; None for no child), return its maximum depth (number of nodes on the longest root-to-leaf path).

## Worked solution and explanation

### Why this problem exists in real interviews

This tests **recursive tree traversal** and the concept of depth in a binary tree. It probes whether a candidate can write a clean recursive solution with correct base cases.

---

### Break down the requirements

#### Step 1: Define the base case

If the node is None, the depth is 0.

#### Step 2: Recursively compute the depth of each subtree

The depth of a node is 1 plus the maximum depth of its left and right children.

---

### The solution

**Recursive depth-first traversal**

```python
def max_depth(root) -> int:
    if root is None:
        return 0
    left_depth = max_depth(root.left)
    right_depth = max_depth(root.right)
    result = 1 + max(left_depth, right_depth)
    return result
```

> **Time and Space Complexity**
>
> **Time:** O(n) where n is the number of nodes. Each node is visited exactly once.
> 
> **Space:** O(h) where h is the height of the tree, due to the recursion stack. In the worst case (skewed tree), this is O(n).

> **Interviewers Watch For**
>
> Clear articulation of the base case. The depth of an empty tree is 0, not -1 or 1. Getting this wrong shifts all depth values.

> **Common Pitfall**
>
> Confusing depth (root-to-node distance) with height (node-to-leaf distance). For the root, they happen to be equivalent, but the distinction matters in follow-ups.

---

## Common follow-up questions

- How would you compute the depth iteratively? _(Tests BFS level-by-level traversal, counting the number of levels.)_
- What if the tree was extremely deep (100K levels)? _(Tests awareness of Python's recursion limit and the need for an iterative approach.)_
- How would you find the minimum depth instead? _(Tests modifying the recursion to stop at the first leaf node.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_tree_measurer)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.