Lesson 17.2 · Binary Search Trees

Validating a BST with Ranges

Checking each node against its parent isn't enough. Every node must fall inside a range inherited from all of its ancestors.

10 min

Think of it like this

Seating guests by age: someone in the "over-50" section, then in its "under-60" row, must be between 50 and 60. Looking only at their immediate neighbour misses the section rule.

1.Why the local check fails

In [5, 1, 6, null, null, 3, 7], each parent-child pair looks fine (3 < 6, 7 > 6), but 3 sits in 5's right subtree and is smaller than 5. Pass a range (low, high) down: going left sets high = node's value, going right sets low = node's value.

An equivalent check: the in-order walk must be strictly increasing.

Main.java

class TreeNode {
    int val; TreeNode left, right;
    TreeNode(int v, TreeNode l, TreeNode r) { val = v; left = l; right = r; }
    TreeNode(int v) { this(v, null, null); }
}

public class Main {
    static boolean local(TreeNode n) {
        if (n == null) return true;
        if (n.left != null && n.left.val >= n.val) return false;
        if (n.right != null && n.right.val <= n.val) return false;
        return local(n.left) && local(n.right);
    }
    static boolean range(TreeNode n, long lo, long hi) {
        if (n == null) return true;
        if (n.val <= lo || n.val >= hi) return false;
        return range(n.left, lo, n.val) && range(n.right, n.val, hi);
    }
    public static void main(String[] args) {
        TreeNode root = new TreeNode(5, new TreeNode(1), new TreeNode(6, new TreeNode(3), new TreeNode(7)));
        System.out.println("local check: " + local(root));
        System.out.println("range check: " + range(root, Long.MIN_VALUE, Long.MAX_VALUE));
    }
}

Output

local check: true
range check: false

Remember

Pass (low, high) down the tree.
Use long bounds so Integer.MIN_VALUE and MAX_VALUE nodes work.
Or check that in-order is strictly increasing.

Common mistakes

Comparing only with the parent.
Using int bounds that collide with real values.

Command Palette

Validating a BST with Ranges

1.Why the local check fails