🔎

BST Operations — Validate, Search, Construct

Exploit the BST invariant (left < root < right) to eliminate half the tree per step. Validate by propagating bounds down. Search by comparing and going left or right. Build balanced BST by always picking the array midpoint as root.

✅ Validate: pass min/max bounds 🔍 Search: compare & branch 🏗 Build: midpoint = root Search O(log n) Validate O(n) Space O(h)

📋 Key Techniques

Use BST property (left < root < right) to eliminate half the tree per step — O(log n)
Validate: pass min/max bounds down; any violation = invalid BST
Search/Insert: compare with node, recurse left or right
Build balanced BST: always pick array midpoint as root
In-order = sorted: validate or list BST values using in-order traversal
BST height: O(log n) balanced, O(n) skewed

💡 Invalid BST trap: checking only parent–child is insufficient. Node 6 under node 3 violates the ancestor bound of 5 even though 6 > 3. Always propagate full (min, max) range down the tree.

⚡ Complexity

Search / Insert

O(h)

Stack Space

O(h)

Validate

O(n)

Build BST

O(n)

Where h = height of tree. Balanced BST: h = O(log n). Skewed BST: h = O(n).
Validate visits every node once — O(n) always.
Build from sorted array creates all n nodes — O(n).

Problem Given a BST [root=5, left=[3,1,4], right=[7,6,8]] and target = 6, search for the node with that value. Compare at each node: go right if target > node, go left if target < node — half the tree is pruned at every step.
Input: BST root = [5,3,7,1,4,6,8], target = 6 · Answer: found at depth 2 (5 → right → 7 → left → 6)

Step 0 / 10

🔍 Init 📐 Check Bounds ✓ Valid ✗ Invalid ✅ Done

✅ Validate BST: propagate (min, max) bounds down the tree. Every node must satisfy min < node.val < max. Any violation means the tree is not a valid BST.

// validate(root, Long.MIN_VALUE, Long.MAX_VALUE)

🌲 Valid BST — propagating bounds

Call Stack

Valid / Found

Checking

Invalid

Search path

Build node

Pattern Skeleton Java 8

// ─── Validate BST (pass bounds down) ─────────────────
boolean validate(TreeNode n, long min, long max) {
    if (n == null) return true;
    if (n.val <= min || n.val >= max) return false;
    return validate(n.left,  min, n.val)        // left:  (min, n.val)
        && validate(n.right, n.val, max);        // right: (n.val, max)
}
// Call: validate(root, Long.MIN_VALUE, Long.MAX_VALUE)

// ─── Search in BST ────────────────────────────────────
TreeNode search(TreeNode n, int target) {
    if (n == null || n.val == target) return n;
    return target < n.val
        ? search(n.left,  target)               // go left
        : search(n.right, target);              // go right
}

// ─── Build Balanced BST from Sorted Array ────────────
TreeNode build(int[] a, int lo, int hi) {
    if (lo > hi) return null;
    int mid = (lo + hi) / 2;
    TreeNode n = new TreeNode(a[mid]);
    n.left  = build(a, lo,      mid - 1);
    n.right = build(a, mid + 1, hi);
    return n;
}
// Call: build(arr, 0, arr.length - 1)

Practice Problems

#98 Validate Binary Search Tree bounds propagation Medium #700 Search in a Binary Search Tree compare & branch Easy #701 Insert into a Binary Search Tree search + insert at null Medium #108 Convert Sorted Array to BST midpoint as root Easy #230 Kth Smallest Element in a BST in-order traversal Medium #235 Lowest Common Ancestor of BST both sides check Medium #110 Balanced Binary Tree post-order height check Easy