Skip to content

Validate BST with Range

The Trap That Gets Everyone

Problem (LC 98): Given a binary tree, determine if it is a valid BST.

Your first instinct: check that every node's left child is smaller and right child is larger.

        5
       / \
      1   7
     / \
    0   6

Node 5: left child 1 < 5, right child 7 > 5. Pass. Node 1: left child 0 < 1, right child 6 > 1. Pass.

Every node passes the local check. But this is not a valid BST.

The problem is node 6. It sits in the left subtree of 5, but 6 > 5. The BST property says everything in the left subtree of 5 must be less than 5. Node 6 violates this — but you'd never catch it by only comparing parent-child pairs.

Checking left < parent < right is not enough. The BST property is global: every node must fall within a valid range inherited from its ancestors.

Valid range narrows at each level: left tightens the upper bound, right tightens the lower bound

The Fix: Pass the Range Down

This is a top-down approach — the preorder pattern from Chapter 4 applied to BSTs.

The idea: as you recurse down the tree, carry a valid range (minVal, maxVal) for the current node. The root can be anything: range is \((-\infty, +\infty)\). When you go left, the current node's value becomes the new upper bound. When you go right, the current node's value becomes the new lower bound.

For our invalid tree:

Node Valid Range Value In Range?
5 \((-\infty, +\infty)\) 5 Yes
1 (left of 5) \((-\infty, 5)\) 1 Yes
7 (right of 5) \((5, +\infty)\) 7 Yes
0 (left of 1) \((-\infty, 1)\) 0 Yes
6 (right of 1) \((1, 5)\) 6 No — \(6 \geq 5\)

Caught. Node 6 must be in range \((1, 5)\) because it's in the right subtree of 1 (so \(> 1\)) and the left subtree of 5 (so \(< 5\)). The value 6 violates the upper bound.

Full Trace on a Valid BST

        5
       / \
      3   7
     / \ / \
    2  4 6  8
Node Valid Range Value In Range? New ranges passed to children
5 \((-\infty, +\infty)\) 5 Yes Left: \((-\infty, 5)\), Right: \((5, +\infty)\)
3 \((-\infty, 5)\) 3 Yes Left: \((-\infty, 3)\), Right: \((3, 5)\)
2 \((-\infty, 3)\) 2 Yes Left: \((-\infty, 2)\), Right: \((2, 3)\)
4 \((3, 5)\) 4 Yes Left: \((3, 4)\), Right: \((4, 5)\)
7 \((5, +\infty)\) 7 Yes Left: \((5, 7)\), Right: \((7, +\infty)\)
6 \((5, 7)\) 6 Yes Left: \((5, 6)\), Right: \((6, 7)\)
8 \((7, +\infty)\) 8 Yes Left: \((7, 8)\), Right: \((8, +\infty)\)

Every node passes. Valid BST.

The range narrows at every level. By the time you reach a leaf, the range is tight — there's exactly one valid interval for each position in the tree.

The Code

bool validate(TreeNode* node, long long minVal, long long maxVal) {
    if (!node) return true;
    if (node->value <= minVal || node->value >= maxVal) return false;
    return validate(node->left, minVal, node->value) &&
           validate(node->right, node->value, maxVal);
}

bool isValidBST(TreeNode* root) {
    return validate(root, -2e18, 2e18);
}

We use long long with \(\pm 2 \times 10^{18}\) as initial bounds to avoid overflow issues when node values can be INT_MIN or INT_MAX.

Complexity: \(O(n)\) time (visit every node once), \(O(h)\) space (recursion stack).

Inorder violations reveal the two swapped nodes in a corrupted BST

Recover BST: Finding Two Swapped Nodes

Problem (LC 99): Two nodes in a valid BST were swapped by mistake. Fix the tree without changing its structure.

The key observation: inorder traversal of a BST gives sorted order. If two nodes are swapped, the inorder sequence will have violations — places where a value is larger than the next value.

Example — nodes 3 and 7 are swapped:

        5
       / \
      7   3
     / \ / \
    2  4 6  8

Inorder: 2, 7, 4, 5, 6, 3, 8

The sorted version should be: 2, 3, 4, 5, 6, 7, 8

Find the violations — positions where previous > current:

Position Previous Current Violation?
1 → 2 2 7 No
2 → 3 7 4 Yes — first violation
3 → 4 4 5 No
4 → 5 5 6 No
5 → 6 6 3 Yes — second violation
6 → 7 3 8 No

Two violations found. The first swapped node is the previous at the first violation (7). The second swapped node is the current at the last violation (3). Swap them back.

Why "first previous" and "last current"? If two adjacent nodes are swapped, there's only one violation — you need previous and current from that single violation. If the swapped nodes are far apart, there are two violations, and the pattern above applies. Using "first previous, last current" handles both cases.

The Code

void findSwapped(TreeNode* node, TreeNode*& previous,
                 TreeNode*& firstViolation, TreeNode*& secondViolation) {
    if (!node) return;

    findSwapped(node->left, previous, firstViolation, secondViolation);

    if (previous && previous->value > node->value) {
        if (!firstViolation) firstViolation = previous;
        secondViolation = node;
    }
    previous = node;

    findSwapped(node->right, previous, firstViolation, secondViolation);
}

void recoverTree(TreeNode* root) {
    TreeNode* previous = nullptr;
    TreeNode* firstViolation = nullptr;
    TreeNode* secondViolation = nullptr;

    findSwapped(root, previous, firstViolation, secondViolation);

    swap(firstViolation->value, secondViolation->value);
}

This is an inorder traversal with state — we track previous to detect out-of-order pairs. The references (TreeNode*&) let the state persist across recursive calls.

Complexity: \(O(n)\) time, \(O(h)\) space.

Try It

The starter code has a tree where node 6 is in the wrong position. Run isValidBST and verify it returns false.

Predict before running: What does validate return on an empty tree (nullptr)? Trace: base case returns true. Correct — an empty tree is trivially a valid BST.

Challenge: Can you validate a BST using inorder traversal instead of the range technique? (Hint: do inorder, check that each value is strictly greater than the previous one. Same \(O(n)\) time, different approach.)

Challenge 2: In the recover problem, what if three or more nodes were swapped? The two-violation approach breaks. Why? (Because with three swaps, you can have up to three violations, and you can't determine which nodes to swap without trying all permutations.)

Edge Cases to Watch For

  • Node values at INT_MIN or INT_MAX: If you use int for the range bounds, the initial range \((-\infty, +\infty)\) can't be represented. Use long long with values like \(\pm 2 \times 10^{18}\), or use optional<int> / nullptr sentinels to represent unbounded ranges.
  • Equal values fail BST validity: The BST property requires strict inequality (\(<\), not \(\leq\)). Node 5 with left child 5 is invalid. Make sure your comparisons use node->value <= minVal || node->value >= maxVal with strict bounds, not < / >.
  • Two adjacent nodes swapped (Recover BST): Only one violation appears in the inorder sequence instead of two. The algorithm must handle this by setting firstViolation = previous and secondViolation = current from the same single violation.

Problems

Problem Link Difficulty
LC 98 — Validate BST leetcode.com/problems/validate-binary-search-tree Medium
LC 99 — Recover BST leetcode.com/problems/recover-binary-search-tree Medium