The Tree Measurer

An easy Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
easy
Seniority
L3
Asked in
Rackspace Technology

Problem

Given the root of a binary tree, return its maximum depth (the number of nodes on the longest root-to-leaf path). Each node is a nested dict with keys 'val', 'left', and 'right', where a missing child is None (null). An empty tree (root is None) has depth 0.

How deep does the rabbit hole go?

Example 1

Input:

root = {"val":3,"left":{"val":9,"left":null,"right":null},"right":{"val":20,"left":{"val":15,"left":null,"right":null},"right":{"val":7,"left":null,"right":null}}}

Output:

3

Example 2

Input:

root = {"val":1,"left":null,"right":{"val":2,"left":null,"right":null}}

Output:

2

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 while navigating the tree's dict-based node representation.

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

Each node is a dict, so read its children with node['left'] and node['right']. The depth of a node is 1 plus the maximum depth of its left and right children.

The solution

Recursive depth-first traversal
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

Common follow-up questions