# The Order Inspector

> A binary tree has rules - is this one actually following them?

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

Domain: Python · Difficulty: medium · Seniority: L4

## Problem

Given a tree stored as a dict where each node name maps to {'val', 'left', 'right'} (left/right point to another node name or None) and a root node name, return True if the tree is a valid BST (strictly, no duplicates: left subtree < node < right subtree).

## Worked solution and explanation

### Why this problem exists in real interviews

This tests **BST validation using range constraints**, a classic recursive problem. It checks whether candidates understand that a valid BST requires every node to satisfy bounds inherited from its ancestors, not just its immediate parent.

> **Trick to Solving**
>
> Pass min and max bounds down the recursion. A node's value must be within `(min_bound, max_bound)`. When going left, update the upper bound. When going right, update the lower bound. This catches violations that comparing only parent-child misses.

---

### Break down the requirements

#### Step 1: Start with the root and infinite bounds

The root can have any value, so initialize with `(-infinity, +infinity)`.

#### Step 2: Validate the current node against bounds

If the node's value is outside `(min_bound, max_bound)`, the tree is invalid.

#### Step 3: Recurse with tightened bounds

For the left child, the upper bound becomes the current node's value. For the right child, the lower bound becomes the current node's value.

---

### The solution

**Recursive validation with inherited bounds**

```python
def is_valid_bst(tree, root_name):
    def validate(name, min_val, max_val):
        if name is None:
            return True
        node = tree[name]
        val = node['val']
        if val <= min_val or val >= max_val:
            return False
        left_valid = validate(node.get('left'), min_val, val)
        right_valid = validate(node.get('right'), val, max_val)
        return left_valid and right_valid
    return validate(root_name, float('-inf'), float('inf'))
```

> **Time and Space Complexity**
>
> **Time:** O(n) where n is the number of nodes. Each node is visited once.
> 
> **Space:** O(h) for the recursion stack where h is the tree height.

> **Interviewers Watch For**
>
> Do you use strict inequality (`<` and `>`)? BSTs typically require strict ordering (no duplicates). Using `<=` would incorrectly allow duplicate values that violate BST property.

> **Common Pitfall**
>
> Only comparing a node with its direct parent. The tree `[5, [3, [4]], [7]]` has 4 in the left subtree of 5 but is the right child of 3. Comparing 4 only with 3 misses that 4 should be less than 5.

---

## Common follow-up questions

- How would you validate a BST using in-order traversal? _(Tests that in-order traversal of a valid BST produces a strictly increasing sequence.)_
- What if the BST allowed duplicate values on the left? _(Tests adjusting bounds to use `<=` for left children.)_
- What if the tree were extremely deep? _(Tests iterative validation with an explicit stack to avoid recursion limits.)_
- How would you fix an invalid BST with minimal changes? _(Tests finding the two swapped nodes and correcting them.)_

## Related

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