The Order Inspector

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

Problem

Return whether the in-memory index we use for ID lookups is a valid binary search tree: every value in a node's left subtree must be smaller than the node and every value in its right subtree larger, so two nodes holding the same ID make it invalid. We keep the index in tree, a dict keyed by node name where each node carries its val and the names of its left and right children (None when a child is missing), and root_name names the top node.

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

Example 1

Input:

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

Output:

true

Example 2

Input:

tree = {"rl":{"val":3,"left":null,"right":null},"left":{"val":1,"left":null,"right":null},"root":{"val":5,"left":"left","right":"right"},"right":{"val":4,"left":"rl","right":null}}, root_name = "root"

Output:

false

Worked solution and explanation

What this really is

This is an interval check dressed up as a tree question. A node does not answer to its parent: it answers to an open range built from every ancestor above it. Almost everyone writes the check that each node sits between its two children. The candidates who pass notice that a value can be perfectly ordered against its parent and still be on the wrong side of its grandparent. Miss that and a tree with 12 tucked under the left side of 10 comes back True, and every lookup for 12 walks right from the root and never finds it.

Parent-only check
At each node, test that the left child is smaller and the right child larger. On the tree with 10 at the root, 5 on its left, and 12 as the right child of 5, every pair is ordered (5 < 12, 5 < 10), so the check says valid.
Inherited range
Carry (min_val, max_val) down the recursion. 5 goes left of 10 and gets the range below 10; 12 goes right of 5 and inherits (5, 10). Because 12 >= 10, the check rejects it.

Building it

Step 1: Give the root an unbounded range

Nothing sits above the root, so it starts with float('-inf') and float('inf'). Using real infinities instead of None sentinels keeps the comparison a single line with no special cases.

Step 2: Reject on equality too

The test is val <= min_val or val >= max_val. An ID equal to an ancestor's is a collision in a lookup index, so equality fails exactly like being out of range. This is the line that sinks the root 6 with a right child 6.

Step 3: Tighten one side per step down

Going left, the node's own val becomes the new upper bound and the lower bound passes through untouched. Going right, it becomes the new lower bound. That pass-through is the whole point: the 10 from the root still caps 12 two levels down.

Step 4: Let a missing child pass

A child name of None is an empty subtree, and an empty subtree breaks no rule, so the helper returns True before it ever looks the name up in tree.

Recursive validation with inherited bounds
def verify_tree_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'))

Common follow-up questions