LeetCode 98 · Trees

Validate Binary Search Tree, explained with a picture

Every branch has a fence of allowed values.

MediumTrees
▶ Watch it step by step

The problem

Decide whether a binary tree is a valid binary search tree: for every node, all values in its left subtree are smaller and all values in its right subtree are larger.

Input:  [5, 3, 8, 1, 6, 7, 9]
Output: false   (6 is in the left side of 5 but is bigger than 5)

Picture it

Picture every branch carrying a fence: a range of allowed values (low, high). The root may hold anything. Going left, the high end of the fence becomes the parent’s value; going right, the low end does. A node outside its fence breaks the rule, even if it looks fine next to its direct parent.

How to recognise it

  • The input is a binary tree and the question is a yes/no check that every node must pass.
  • The rule for a node depends on its ancestors, not only its parent ("all values in the left subtree"). That points to passing information down a depth-first search (DFS: follow one branch to the bottom before trying the next).
  • Each step down narrows a range: going left caps the maximum, going right raises the minimum, so pass (low, high) bounds as arguments.
  • Up to about 10^4 nodes, so each node should be visited a constant number of times.

Start with brute force

Follow the definition literally. For every node, collect every value in its left subtree and check they are all smaller, then collect the right subtree and check they are all larger. Then repeat for both children.

def values(node):
    if not node:
        return []
    return values(node.left) + [node.val] + values(node.right)

def is_valid_bst_brute(root):
    if not root:
        return True
    if any(v >= root.val for v in values(root.left)):
        return False
    if any(v <= root.val for v in values(root.right)):
        return False
    return is_valid_bst_brute(root.left) and is_valid_bst_brute(root.right)

It is correct, but each node is collected again for every ancestor: O(n log n) on a balanced tree, O(n²) on a chain (about 5 × 10^7 copies for 10^4 nodes). Space is O(n) for the lists.

From brute force to the idea

  1. Find the waste. The brute force collects whole subtrees only to learn the largest value on the left and the smallest on the right, and every ancestor re-checks the same nodes.
  2. Flip the direction. Instead of ancestors looking down, let each node carry down what its ancestors require: the range it must fall inside.
  3. Start wide open. The root may hold any value: its range is (−infinity, +infinity).
  4. Tighten on the way down. Going left, the upper bound becomes the parent's value; going right, the lower bound does. The other bound is inherited, which is how a grandparent's rule reaches a grandchild.
  5. Check once per node. If lo < node.val < hi fails, return False. An empty child is always fine.

This is the key idea: pass (low, high) bounds down the tree and tighten them at each step.

The key idea

Pass (low, high) bounds down the tree and tighten them at each step. O(n).

Python solution

def is_valid_bst(root):
    def check(node, lo, hi):
        if not node:
            return True
        if not (lo < node.val < hi):
            return False
        return check(node.left, lo, node.val) and check(node.right, node.val, hi)
    return check(root, -inf, inf)

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from math import inf

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n log n) balanced, O(n²) chain: subtrees are re-collected for every ancestorO(n): the collected value lists
Bounds DFS (shown code)O(n): each node is checked once with two comparisonsO(h): one call per level of the recursion, h is the tree height (n for a chain)

Edge cases

  • Empty tree (root is None): returns True.
  • Single node: returns True.
  • Duplicate values (a 2 with a left child 2): returns False, because the check is strict (<) and this problem forbids duplicates.
  • Grandchild breaks an ancestor's rule ([5, 4, 6, null, null, 3, 7]): returns False; the 3 is right of 5, and the inherited lower bound 5 catches it.
  • Extreme values (−2^31 or 2^31 − 1): returns True, because the starting bounds are infinite, not integer limits. The code needs from math import inf.
  • Very deep tree: a chain of about 1,000 nodes hits Python's default recursion limit and raises RecursionError. Raise the limit or use an explicit stack.

Common mistakes

  • Comparing each node only with its own children. That accepts [5, 4, 6, null, null, 3, 7], where 3 is less than 6 but sits to the right of 5.
  • Starting the bounds at the smallest and largest 32-bit integers, which wrongly rejects a node that holds exactly that value.
  • Using <= in the check, which accepts duplicates the problem forbids.
Your turn: duplicates allowed on the left

Some textbooks allow equal values, as long as they go left: every value in the left subtree is less than or equal to the node, and every value in the right subtree is strictly greater. Change the check for this rule. Describe your approach, then write it if you like.

Compare with our answer

Keep the same bounds DFS. Only the comparison changes: a node may now equal its upper bound (which came from an ancestor it sits to the left of), but must still be strictly greater than its lower bound.

from math import inf

def is_valid_bst_dup_left(root):
    def check(node, lo, hi):
        if not node:
            return True
        if not (lo < node.val <= hi):
            return False
        return check(node.left, lo, node.val) and check(node.right, node.val, hi)
    return check(root, -inf, inf)

A 2 with a left child 2 is now valid; a 2 with a right child 2 is still invalid. Time O(n), space O(h).

A strong answer mentions: which side of the comparison becomes <= and why, that the bounds are passed down exactly as before, and a test with equal values on each side.

Check what stuck

1. You must check that every node in a binary tree lies within 10 of every one of its ancestors. Which approach fits best?

2. Why does the shown solution use O(h) extra space rather than O(n)?

3. A learner starts the recursion with check(root, -2**31, 2**31 - 1). Which tree is now judged wrongly?

Score 60% or more and the lesson is marked complete.