The Family Reunion

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

Domain
Python
Difficulty
medium
Seniority
L4
Asked in
Citadel

Problem

Given the root of a binary search tree (as nested dicts with keys 'val', 'left', 'right', where a missing child is null/None) and two integer values p and q present in the BST, return the value of their lowest common ancestor.

Two cousins share a common ancestor somewhere above.

Example 1

Input:

root = {"val":6,"left":{"val":2,"left":{"val":0,"left":null,"right":null},"right":{"val":4,"left":{"val":3,"left":null,"right":null},"right":{"val":5,"left":null,"right":null}}},"right":{"val":8,"left":{"val":7,"left":null,"right":null},"right":{"val":9,"left":null,"right":null}}}, p = 2, q = 8

Output:

6

Example 2

Input:

root = {"val":6,"left":{"val":2,"left":{"val":0,"left":null,"right":null},"right":{"val":4,"left":null,"right":null}},"right":{"val":8,"left":null,"right":null}}, p = 2, q = 4

Output:

2

Worked solution and explanation

Why this problem exists in real interviews

This tests lowest common ancestor (LCA) in a BST, which uses the BST ordering property for an efficient solution. It probes tree traversal and the ability to exploit data structure invariants. Here the tree arrives as nested dicts, so you must also navigate it by key (node['val'], node['left'], node['right']) rather than attribute access.

Break down the requirements

Step 1: Start at the root

The LCA must be on the path from root to both target nodes. Each node is a dict, so read its value with node['val'] and step into children with node['left'] / node['right'], where a null child is None.

Step 2: Use BST ordering to navigate

If both values are less than the current node's value, the LCA is in the left subtree. If both are greater, it is in the right subtree.

Step 3: Return when values split

When one value is less and the other is greater (or one equals the current node's value), the current node is the LCA. Return its value.

The solution

BST-property guided traversal
def lowest_common_ancestor(root, p: int, q: int):
    node = root
    while node is not None:
        val = node["val"]
        if p < val and q < val:
            node = node["left"]
        elif p > val and q > val:
            node = node["right"]
        else:
            return val
    return None

Common follow-up questions