Week 4 · Trees

Validate Binary Search Tree

Given a binary tree, decide whether every node satisfies the full binary-search-tree ordering rule: all values in the left subtree are smaller than the node, and all values in the right subtree are larger.

Medium Trees Week 4 Practice runner

Frame the problem

A node's value must be checked against all ancestor bounds, not only its parent.
Duplicates are invalid for the common LeetCode version.
The tree may be skewed, so recursion depth can become O(n).

1. Reveal example inputs and outputs

Example 1

Input:

is_valid_bst([
  2,
  [
    1,
    null,
    null
  ],
  [
    3,
    null,
    null
  ]
])

Output:

true

Example 2

Input:

is_valid_bst([
  5,
  [
    1,
    null,
    null
  ],
  [
    4,
    [
      3,
      null,
      null
    ],
    [
      6,
      null,
      null
    ]
  ]
])

Output:

false

2. Brute force first

If you gathered every subtree's min and max, what would each recursive call need to return to the parent?

3. Reveal the insight ladder

A local parent-child comparison is insufficient.
Each recursive call should know the allowed open interval for its node.
Going left tightens the upper bound to the current value.
Going right tightens the lower bound to the current value.

4. Dry run before code

Tree: 10 with left child 5, and 5 has right child 12.
Root 10 is allowed inside (-inf, inf).
Left child 5 is allowed inside (-inf, 10).
Node 12 is in the left subtree of 10, so it is still constrained by upper bound 10. 12 violates that bound.

5. Reveal final Python solution

def is_valid_bst(root):
    def dfs(node, low, high):
        if node is None:
            return True
        value, left, right = node
        if not low < value < high:
            return False
        return dfs(left, low, value) and dfs(right, value, high)

    return dfs(root, float("-inf"), float("inf"))

Complexity: Time O(n), because each node is visited once. Space O(h), where h is the tree height from recursion stack usage.

Interview narration

The invariant is that every recursive call receives the complete valid range from its ancestors.
I use open bounds because duplicates are not valid in this problem.
This catches violations that are several levels below the ancestor they break.

Common traps

Only checking node.left < node < node.right.
Allowing duplicate values through <= or >=.
Forgetting that a right child inside a left subtree is still bounded by the root.

C and C++ note

In C or C++, avoid sentinel integer bounds if node values can equal INT_MIN or INT_MAX. Prefer nullable bounds or wider integer types.

Follow-up drills

1. Can you solve it with inorder traversal and a previous value?

Yes. Inorder traversal of a valid BST produces a strictly increasing sequence. Track the previous visited value; if the current value is less than or equal to it, return false. This is clean, but the bound-based version often explains ancestor constraints more directly.

2. How would the logic change if duplicates were allowed on one side?

Change the bound rule from open intervals to match the policy. For example, duplicates allowed on the right could use left subtree values < node and right subtree values >= node. Be explicit because different interviewers use different duplicate conventions.

3. How would you avoid recursion depth issues for a very skewed tree?

Use an explicit stack. Push tuples of (node, low, high) for the bound-based approach, or do iterative inorder traversal with a previous value. The time stays O(n); stack space remains O(h), but you avoid Python recursion limits.

Interactive runner

Write the required Python function. Your code runs locally in this browser. Hints reveal one failing case at a time.