L3 · FAANGTrees~15 min · 6 tests

Validate a Binary Search Tree

Check whether a binary tree is a valid BST by passing allowed (low, high) bounds down the recursion in O(n). Avoid the classic parent-only comparison bug.

The problem

Return True if the tree is a valid binary search tree: every value in a node's left subtree is strictly smaller than it, and every value in its right subtree is strictly larger.

TreeNode and build_tree are provided (see the previous question).

Examples

Example 1
Input
```
is_valid_bst(build_tree([2, 1, 3]))
```
Expected output
```
True
```

Example 2

Input

is_valid_bst(build_tree([5, 1, 4, None, None, 3, 6]))

Expected output

False

+ 4 hidden tests on Submit — 3 is in the right subtree of 5, duplicates are not allowed.

Edge cases to ask about

Grandchild violates the root
Duplicates
Empty tree

How the tests call your code

These helpers run before your code. The test inputs above call them.

from collections import deque as _deque


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def build_tree(values):
    """Level-order list -> tree. None marks a missing child: [3, 9, 20, None, None, 15, 7]."""
    if not values or values[0] is None:
        return None
    root = TreeNode(values[0])
    queue, i = _deque([root]), 1
    while queue and i < len(values):
        node = queue.popleft()
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i]); queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i]); queue.append(node.right)
        i += 1
    return root


def tree_values(root):
    """Tree -> level-order list with trailing Nones trimmed (the inverse of build_tree)."""
    out, queue = [], _deque([root])
    while queue:
        node = queue.popleft()
        if node is None:
            out.append(None)
            continue
        out.append(node.val)
        queue.append(node.left)
        queue.append(node.right)
    while out and out[-1] is None:
        out.pop()
    return out

Hints

0/3

How an interviewer scores this

0/9

1. Understand the problemRestate it, ask about edge cases and input size.
2. Write a brute-force solutionCorrect first, clever later.
3. Get the correct outputautoAll visible examples pass.
4. Analyse time complexityautoCommit to a Big-O in the Complexity Lab.
5. Analyse space complexityautoExtra memory, not the input.
6. Identify the bottleneckautoMeasure your code — where does it bend?
7. OptimiseUsually: a set or dict instead of a scan.
8. Explain why it worksSay it out loud to Solvi.
9. Test the edge casesautoSubmit passes every hidden test.

Python 3.13 · is_valid_bst

def is_valid_bst(root):
    """True if the tree is a strict BST."""
    # Write your solution here
    pass

⌘/Ctrl + Enter runs the examples

Your code runs in real CPython inside your browser — nothing is sent anywhere. The first run downloads the interpreter (about 6 MB, once). Your code is saved on this device as you type.

Complexity Lab

What does this cost as n grows?

Interviewers score the analysis as much as the code. Commit to an answer first — then check it, and read why.

Time complexity of the optimal solution

Space complexity (extra memory)

Pick both to reveal the answer.

From brute force to optimal

The progression an interviewer wants to hear, one step at a time.

Approach	Time	Space	Idea
Compare each node only with its children	O(n)	O(h)	WRONG — misses a grandchild breaking the rule.
Pass (low, high) bounds down	O(n)	O(h)	Each node must lie strictly inside the bounds its ancestors set.
bestIn-order traversal is strictly increasing	O(n)	O(h)

Walkthrough of the optimal approach (try it yourself first)

The common bug is comparing a node only with its direct children: in [5, 4, 6, null, null, 3, 7], node 3 is fine next to its parent 6 but sits in the right subtree of 5. Carry the allowed open interval (low, high) down instead: a left child must be below its parent, a right child above, and both must stay inside the ancestors' bounds.

The iterative stack avoids recursion limits on a deep, skewed tree.

Complexity: O(n) time, O(h) space. Each node is checked once; the stack holds at most one path's worth of pending siblings.

Reveal the reference solution

def is_valid_bst(root):
    stack = [(root, float("-inf"), float("inf"))]
    while stack:
        node, low, high = stack.pop()
        if node is None:
            continue
        if not low < node.val < high:
            return False
        stack.append((node.left, low, node.val))
        stack.append((node.right, node.val, high))
    return True

Follow-ups interviewers ask

Recover a BST where two nodes were swapped.
Use the in-order approach.

Frequently asked interview questions

Core interview concepts, complexities, and follow-ups scored by hiring teams.

What is the time complexity of Validate a Binary Search Tree in Python?

The optimal solution runs in O(n) time and O(h) auxiliary space. Each node is checked once; the stack holds at most one path's worth of pending siblings.

What is the brute-force approach, and how do you optimise it?

Compare each node only with its children: O(n) time, O(h) space. WRONG — misses a grandchild breaking the rule. Pass (low, high) bounds down: O(n) time, O(h) space. Each node must lie strictly inside the bounds its ancestors set. In-order traversal is strictly increasing: O(n) time, O(h) space.

What follow-up questions do interviewers ask about Validate a Binary Search Tree?

Recover a BST where two nodes were swapped. Use the in-order approach.