# The Family Reunion

> Two cousins share a common ancestor somewhere above.

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

Domain: Python · Difficulty: medium · Seniority: L4

## Problem

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

## 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.

> **Trick to Solving**
>
> In a BST, the LCA is the first node where the two values split (one goes left, one goes right). If both values are smaller, go left. If both are larger, go right. Otherwise, you are at the LCA.

---

### Break down the requirements

#### Step 1: Start at the root

The LCA must be on the path from root to both target nodes.

#### Step 2: Use BST ordering to navigate

If both values are less than the current node, 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), the current node is the LCA.

---

### The solution

**BST-property guided traversal**

```python
def lowest_common_ancestor(root, p: int, q: int):
    node = root
    while node is not None:
        if p < node.val and q < node.val:
            node = node.left
        elif p > node.val and q > node.val:
            node = node.right
        else:
            return node.val
    return None
```

> **Time and Space Complexity**
>
> **Time:** O(h) where h is the height of the tree. O(log n) for balanced BSTs, O(n) for skewed.
> 
> **Space:** O(1). Iterative traversal uses no extra space.

> **Interviewers Watch For**
>
> Whether you exploit the BST property vs using the generic binary tree LCA approach. The BST solution is O(h) time and O(1) space; the generic approach is O(n) time.

> **Common Pitfall**
>
> Assuming the two values are always in the tree. Production code should validate that both values exist before reporting an LCA.

---

## Common follow-up questions

- How would you find the LCA in a generic binary tree (not BST)? _(Tests the recursive approach checking left and right subtrees.)_
- What if you needed to find the LCA of k nodes? _(Tests range-based approach: the LCA is where min(values) and max(values) split.)_
- What if the tree is extremely deep? _(Tests iterative vs recursive to avoid stack overflow.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_family_reunion)
- [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.