Skip to content

086 — Validate Binary Search Tree

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 2 revisions

86 — Validate Binary Search Tree

LeetCode 98 · Medium. Given the root of a binary tree, determine if it is a valid binary search tree — for every node, all values in its left subtree must be strictly less than the node's value, and all values in its right subtree must be strictly greater.

🍽️ Intuition

Here's the trap this problem is designed to catch: it's tempting to check only "is my left child smaller than me, and is my right child bigger than me" at every node — but that's not the actual rule. The rule is about the entire left and right subtrees, not just direct children. A node three levels down on the left could be smaller than its immediate parent but still bigger than some ancestor further up, which would break the BST property just as badly. Every node actually lives inside a valid range — bounded below by the largest ancestor it's a left-descendant of, and bounded above by the smallest ancestor it's a right-descendant of — and that range has to be respected all the way down.

🚩 Pattern-Recognition Cue

"Valid BST" / "every node in the left subtree less than, every node in the right subtree greater than" signals that a plain local check (compare a node only to its direct children) is a bug waiting to happen — you need to thread a shrinking (lowerBound, upperBound) range down through the recursion, tightening it every time you descend left or right.

🐢 Brute Force

Do a full inorder traversal, collecting every value into an array — a BST's inorder traversal is sorted if and only if the tree is valid — then check the array is strictly increasing.

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ val: Int) { self.val = val }
}

func inorder(_ node: TreeNode?, _ values: inout [Int]) {
    guard let node = node else { return }
    inorder(node.left, &values)
    values.append(node.val)
    inorder(node.right, &values)
}

func isValidBSTBruteForce(_ root: TreeNode?) -> Bool {
    var values: [Int] = []
    inorder(root, &values)

    for i in 1..<values.count where values.count > 1 {
        if values[i] <= values[i - 1] { return false }
    }
    return true
}

// smoke test: valid BST  2 -> (1, 3)
let bfValid = TreeNode(2)
bfValid.left = TreeNode(1); bfValid.right = TreeNode(3)
print(isValidBSTBruteForce(bfValid))   // true

// smoke test: invalid BST  5 -> (1, 6 -> (3, 7))  — 3 is < 5 but sits in the right subtree
let bfInvalid = TreeNode(5)
bfInvalid.left = TreeNode(1); bfInvalid.right = TreeNode(6)
bfInvalid.right?.left = TreeNode(3); bfInvalid.right?.right = TreeNode(7)
print(isValidBSTBruteForce(bfInvalid))   // false

Big-O: O(n) time — one inorder pass plus one linear scan of the resulting array. O(n) extra space for the array holding every value.

🚀 Optimal

Recurse down carrying a (lowerBound, upperBound) range. Each node must fall strictly inside its inherited range; descending left tightens the upper bound to the current node's value, descending right tightens the lower bound.

func isValidBST(_ root: TreeNode?) -> Bool {
    func validate(_ node: TreeNode?, _ lower: Int?, _ upper: Int?) -> Bool {
        guard let node = node else { return true }

        if let lower = lower, node.val <= lower { return false }
        if let upper = upper, node.val >= upper { return false }

        return validate(node.left, lower, node.val) && validate(node.right, node.val, upper)
    }

    return validate(root, nil, nil)
}

// smoke test: same trees as above
let valid = TreeNode(2)
valid.left = TreeNode(1); valid.right = TreeNode(3)
print(isValidBST(valid))   // true

let invalid = TreeNode(5)
invalid.left = TreeNode(1); invalid.right = TreeNode(6)
invalid.right?.left = TreeNode(3); invalid.right?.right = TreeNode(7)
print(isValidBST(invalid))   // false — node 3 is visited with bounds (lower: 5, upper: 6) and fails 3 <= 5

// edge case: a tree containing Int.min as a value, at the very left edge
let edge = TreeNode(Int.min)
print(isValidBST(edge))   // true — bounds start as (nil, nil), so no sentinel-value collision occurs

Big-O: O(n) time — each node is visited exactly once. O(h) extra space for the recursion stack, versus the brute force's O(n) array.

🔑 The Key Insight

The brute force works, but it's really smuggling the range-checking logic into a side effect of inorder traversal — "sorted" is just what "every node respects its inherited range" looks like once flattened into a sequence. The optimal version makes that inherited range explicit and checks it directly, node by node, without needing to materialize the whole traversal first. Using Int? (optional) bounds instead of sentinel values like Int.min/Int.max matters here too — if a real node happens to hold the value Int.min itself, a sentinel-based bound would either falsely reject it or fail to bound it at all, while nil cleanly means "no constraint yet" regardless of what values the tree actually contains.

🔗 Related Chapters

  • Binary Search Trees — this problem is entirely about verifying the BST invariant holds at every node, not just between direct parent-child pairs.
  • Binary Trees — the underlying shape being validated.
  • DFS and Backtracking — the recursive descent that threads a shrinking (lowerBound, upperBound) range through each call.

🧸 Memory Sentence

Validate BST is checking that every node lives inside the range its ancestors carved out for it — not just "am I bigger than my left child," but "am I still inside the box my grandparents built."

✅ Check Your Understanding

Trace isValidBST on the tree 5 -> (1, 6 -> (3, 7)). Write out the (lower, upper) bounds passed into every recursive call, and identify exactly which call fails — explain why checking node.left.val < node.val and node.right.val > node.val in isolation, without threading bounds down further, would have missed this particular violation.

⬅️ Previous: Count Good Nodes in Binary Tree · Next: Kth Smallest Element in a BST ➡️

Clone this wiki locally