PK

PKBytes

Explore tracks
Chapter 25: Binary Search Trees and Ordered Sets
25.04Intermediate / Advanced4 topics16 min4 interactive animations

BST validation

Checking and repairing BSTs: validation with bounds, validation by inorder order, recovering two swapped nodes and building a BST from a preorder sequence.

Learning goals

  • Validate a BST with bounds that tighten as the recursion descends
  • Validate with a single inorder pass
  • Locate and fix two swapped keys in one traversal
  • Rebuild a BST from its preorder sequence in linear time

Prerequisites

The BST invariantTraversal methods

Checking only that each node is bigger than its left child and smaller than its right child is the classic wrong answer. The animations show why, and then give two correct ways.

25.04.1

Validate BST with bounds

Pass down the allowed open range (lo, hi) for each subtree: the root may be anything; going left, the node's key becomes the new upper bound; going right, it becomes the new lower bound. A node is valid only when lo < key < hi, and both subtrees must be valid with their own ranges.

The “Only parents checked: invalid” preset (tree “5 1 4 # # 3 6”) is the standard trap: each node is correctly ordered relative to its parent, but 3 sits in the right subtree of 5 and is smaller than 5. The range for 3 is (5, 4), so the animation flags it. The “Duplicate key: invalid” preset (2 with two children 2) fails because the strict rule demands distinct keys; use a different inequality if your policy allows duplicates on one side.

Java
1static boolean isValid(TreeNode n, long lo, long hi) {    // every key must lie strictly between lo and hi
2    if (n == null) return true;
3    if (n.val <= lo || n.val >= hi) return false;
4    return isValid(n.left, lo, n.val) && isValid(n.right, n.val, hi);
5}
6// call: isValid(root, Long.MIN_VALUE, Long.MAX_VALUE)   (long bounds, so Integer.MIN_VALUE keys work)

Best

O(1)

Average

O(n)

Worst

O(n)

Space

O(h)

Validating a BST with bounds or inorder order, and recovering swapped nodes

Interactive · edit the input

Your input

Try

binary tree · 5 nodes

5
1
4
3
6
Current nodeChecked and validVisited in orderViolates the ruleFirst out-of-place nodeSecond out-of-place node
Setup

A BST needs more than 'left < parent < right' at every node: every key in a subtree must stay inside the open range set by all its ancestors. Each node passes its allowed range (lo, hi) down.

Step 1 / 5
Java
1static boolean isValid(TreeNode n, long lo, long hi) {   // every key must lie strictly between lo and hi
2    if (n == null) return true;
3    if (n.val <= lo || n.val >= hi) return false;
4    return isValid(n.left, lo, n.val) && isValid(n.right, n.val, hi);
5}
6static boolean isValidInorder(TreeNode root) {
7    long prev = Long.MIN_VALUE;
8    Deque<TreeNode> stack = new ArrayDeque<>();
9    for (TreeNode n = root; n != null || !stack.isEmpty(); ) {
10        while (n != null) { stack.push(n); n = n.left; }
11        n = stack.pop();
12        if (n.val <= prev) return false;                 // not strictly increasing
13        prev = n.val;
14        n = n.right;
15    }
16    return true;
17}
18static void recover(TreeNode root) {                      // two nodes were swapped: find them in one inorder pass
19    TreeNode first = null, second = null, prev = null;
20    Deque<TreeNode> stack = new ArrayDeque<>();
21    for (TreeNode n = root; n != null || !stack.isEmpty(); ) {
22        while (n != null) { stack.push(n); n = n.left; }
23        n = stack.pop();
24        if (prev != null && prev.val > n.val) {           // a descent
25            if (first == null) first = prev;              // the first descent: the larger key is out of place
26            second = n;                                   // the last descent: the smaller key is out of place
27        }
28        prev = n;
29        n = n.right;
30    }
31    int t = first.val; first.val = second.val; second.val = t;
32}

Live state

No condition evaluated on this step
Execution trace (dry run table)Show 5 steps
StepLineStateWhat happens
1L1A BST needs more than 'left < parent < right' at every node: every key in a subtree must stay inside the open range set by all its ancestors. Each node passes its allowed range (lo, hi) down.
2L3node=5 lo=-inf hi=+inf5 lies strictly between -inf and +inf: allowed here.
3L3node=1 lo=-inf hi=51 lies strictly between -inf and 5: allowed here.
4L3node=4 lo=5 hi=+inf4 is not strictly between 5 and +inf: it breaks the ordering rule imposed by an ancestor, so the tree is not a BST.
5L3result=falsefalse.
25.04.2

Inorder sortedness

The inorder traversal of a BST is strictly increasing, and the converse holds for validity too: a binary tree is a BST exactly when its inorder sequence is strictly increasing. So validate with one inorder pass that remembers the previous key and fails on current <= previous. The iterative version stops at the first violation without finishing the traversal.

In the animation's “Inorder check, invalid” preset the traversal stops as soon as it sees a key that does not exceed its predecessor. Both validation methods are O(n) in time and O(h) in space; the bounds version carries more state per call, and the inorder version carries one number.

Java
1static boolean isValidInorder(TreeNode root) {
2    long prev = Long.MIN_VALUE;
3    Deque<TreeNode> stack = new ArrayDeque<>();
4    for (TreeNode n = root; n != null || !stack.isEmpty(); ) {
5        while (n != null) { stack.push(n); n = n.left; }
6        n = stack.pop();
7        if (n.val <= prev) return false;                  // not strictly increasing
8        prev = n.val;
9        n = n.right;
10    }
11    return true;
12}

Best

O(1)

Average

O(n)

Worst

O(n)

Space

O(h)

Validating a BST with bounds or inorder order, and recovering swapped nodes

Interactive · edit the input

Your input

Try

binary tree · 5 nodes

5
1
4
3
6
Current nodeChecked and validVisited in orderViolates the ruleFirst out-of-place nodeSecond out-of-place node
Setup

A BST needs more than 'left < parent < right' at every node: every key in a subtree must stay inside the open range set by all its ancestors. Each node passes its allowed range (lo, hi) down.

Step 1 / 5
Java
1static boolean isValid(TreeNode n, long lo, long hi) {   // every key must lie strictly between lo and hi
2    if (n == null) return true;
3    if (n.val <= lo || n.val >= hi) return false;
4    return isValid(n.left, lo, n.val) && isValid(n.right, n.val, hi);
5}
6static boolean isValidInorder(TreeNode root) {
7    long prev = Long.MIN_VALUE;
8    Deque<TreeNode> stack = new ArrayDeque<>();
9    for (TreeNode n = root; n != null || !stack.isEmpty(); ) {
10        while (n != null) { stack.push(n); n = n.left; }
11        n = stack.pop();
12        if (n.val <= prev) return false;                 // not strictly increasing
13        prev = n.val;
14        n = n.right;
15    }
16    return true;
17}
18static void recover(TreeNode root) {                      // two nodes were swapped: find them in one inorder pass
19    TreeNode first = null, second = null, prev = null;
20    Deque<TreeNode> stack = new ArrayDeque<>();
21    for (TreeNode n = root; n != null || !stack.isEmpty(); ) {
22        while (n != null) { stack.push(n); n = n.left; }
23        n = stack.pop();
24        if (prev != null && prev.val > n.val) {           // a descent
25            if (first == null) first = prev;              // the first descent: the larger key is out of place
26            second = n;                                   // the last descent: the smaller key is out of place
27        }
28        prev = n;
29        n = n.right;
30    }
31    int t = first.val; first.val = second.val; second.val = t;
32}

Live state

No condition evaluated on this step
Execution trace (dry run table)Show 5 steps
StepLineStateWhat happens
1L1A BST needs more than 'left < parent < right' at every node: every key in a subtree must stay inside the open range set by all its ancestors. Each node passes its allowed range (lo, hi) down.
2L3node=5 lo=-inf hi=+inf5 lies strictly between -inf and +inf: allowed here.
3L3node=1 lo=-inf hi=51 lies strictly between -inf and 5: allowed here.
4L3node=4 lo=5 hi=+inf4 is not strictly between 5 and +inf: it breaks the ordering rule imposed by an ancestor, so the tree is not a BST.
5L3result=falsefalse.
25.04.3

Recover swapped nodes

Two nodes of a valid BST had their keys swapped by mistake. In the inorder sequence the damage shows as **descents**, places where a key is followed by a smaller one. If the swapped keys were adjacent in the sequence there is exactly one descent; otherwise there are two. Take the larger key of the first descent and the smaller key of the last descent, and swap their values back.

The animation's “Recover an adjacent swap (one descent)” preset (tree “3 1 4 # # 2”) has the single descent 3 > 2, so it swaps 3 and 2. The “Recover a distant swap (two descents)” preset (“6 3 8 1 7 5 9”) has inorder 1, 3, 7, 6, 5, 8, 9 with descents 7 > 6 and 6 > 5, so the keys to swap back are the 7 from the first and the 5 from the second. The pass is O(n) time and O(h) space.

Java
1static void recover(TreeNode root) {
2    TreeNode first = null, second = null, prev = null;
3    Deque<TreeNode> stack = new ArrayDeque<>();
4    for (TreeNode n = root; n != null || !stack.isEmpty(); ) {
5        while (n != null) { stack.push(n); n = n.left; }
6        n = stack.pop();
7        if (prev != null && prev.val > n.val) {           // a descent
8            if (first == null) first = prev;              // the first descent: the larger key is out of place
9            second = n;                                   // the last descent: the smaller key is out of place
10        }
11        prev = n;
12        n = n.right;
13    }
14    int t = first.val; first.val = second.val; second.val = t;
15}

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(h)

Validating a BST with bounds or inorder order, and recovering swapped nodes

Interactive · edit the input

Your input

Try

binary tree · 5 nodes

5
1
4
3
6
Current nodeChecked and validVisited in orderViolates the ruleFirst out-of-place nodeSecond out-of-place node
Setup

A BST needs more than 'left < parent < right' at every node: every key in a subtree must stay inside the open range set by all its ancestors. Each node passes its allowed range (lo, hi) down.

Step 1 / 5
Java
1static boolean isValid(TreeNode n, long lo, long hi) {   // every key must lie strictly between lo and hi
2    if (n == null) return true;
3    if (n.val <= lo || n.val >= hi) return false;
4    return isValid(n.left, lo, n.val) && isValid(n.right, n.val, hi);
5}
6static boolean isValidInorder(TreeNode root) {
7    long prev = Long.MIN_VALUE;
8    Deque<TreeNode> stack = new ArrayDeque<>();
9    for (TreeNode n = root; n != null || !stack.isEmpty(); ) {
10        while (n != null) { stack.push(n); n = n.left; }
11        n = stack.pop();
12        if (n.val <= prev) return false;                 // not strictly increasing
13        prev = n.val;
14        n = n.right;
15    }
16    return true;
17}
18static void recover(TreeNode root) {                      // two nodes were swapped: find them in one inorder pass
19    TreeNode first = null, second = null, prev = null;
20    Deque<TreeNode> stack = new ArrayDeque<>();
21    for (TreeNode n = root; n != null || !stack.isEmpty(); ) {
22        while (n != null) { stack.push(n); n = n.left; }
23        n = stack.pop();
24        if (prev != null && prev.val > n.val) {           // a descent
25            if (first == null) first = prev;              // the first descent: the larger key is out of place
26            second = n;                                   // the last descent: the smaller key is out of place
27        }
28        prev = n;
29        n = n.right;
30    }
31    int t = first.val; first.val = second.val; second.val = t;
32}

Live state

No condition evaluated on this step
Execution trace (dry run table)Show 5 steps
StepLineStateWhat happens
1L1A BST needs more than 'left < parent < right' at every node: every key in a subtree must stay inside the open range set by all its ancestors. Each node passes its allowed range (lo, hi) down.
2L3node=5 lo=-inf hi=+inf5 lies strictly between -inf and +inf: allowed here.
3L3node=1 lo=-inf hi=51 lies strictly between -inf and 5: allowed here.
4L3node=4 lo=5 hi=+inf4 is not strictly between 5 and +inf: it breaks the ordering rule imposed by an ancestor, so the tree is not a BST.
5L3result=falsefalse.
25.04.4

BST from preorder

Any sequence of distinct keys is the preorder of exactly one BST, the one built by inserting them in that order, but inserting one by one costs O(n · h). In linear time: pass down an **upper bound**. The next key becomes a node if it is below the bound; its left subtree takes the following keys below the node's key; its right subtree takes the following keys below the inherited bound. A key above the bound ends the current subtree.

The “From a preorder sequence” preset builds the tree for 8, 5, 1, 7, 10, 12 in one pass over the list, consuming each key once. The animation shows the index into the sequence moving forward and the bound being passed down.

Java
1static int idx;
2static TreeNode fromPreorder(int[] pre) {
3    idx = 0;
4    return build(pre, Integer.MAX_VALUE);
5}
6static TreeNode build(int[] pre, int bound) {             // keys of this subtree are below bound
7    if (idx == pre.length || pre[idx] > bound) return null;
8    TreeNode n = new TreeNode(pre[idx++]);
9    n.left = build(pre, n.val);
10    n.right = build(pre, bound);
11    return n;
12}

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(h)

Building a BST: balanced from sorted data, by insertion order, from preorder

Interactive · edit the input

Your input

Try

sorted keys

10
20
30
40
50
60
70
Setup

Sorted keys can be turned into a balanced BST: make the middle key the root and recurse on each half. The two halves differ in size by at most one.

Step 1 / 17
Java
1static TreeNode sortedToBst(int[] a, int lo, int hi) {   // a is sorted and distinct
2    if (lo > hi) return null;
3    int mid = (lo + hi) >>> 1;                   // the middle key becomes the root
4    TreeNode n = new TreeNode(a[mid]);
5    n.left = sortedToBst(a, lo, mid - 1);
6    n.right = sortedToBst(a, mid + 1, hi);
7    return n;
8}
9static TreeNode insert(TreeNode n, int key) {
10    if (n == null) return new TreeNode(key);
11    if (key < n.val) n.left = insert(n.left, key);
12    else if (key > n.val) n.right = insert(n.right, key);
13    return n;
14}
15static int idx;
16static TreeNode fromPreorder(int[] pre, int bound) {     // keys of this subtree are below bound
17    if (idx == pre.length || pre[idx] > bound) return null;
18    TreeNode n = new TreeNode(pre[idx++]);
19    n.left = fromPreorder(pre, n.val);
20    n.right = fromPreorder(pre, bound);
21    return n;
22}

Live state

0 nodes

keys

7

No condition evaluated on this step
Execution trace (dry run table)Show 17 steps
StepLineStateWhat happens
1L1keys=7Sorted keys can be turned into a balanced BST: make the middle key the root and recurse on each half. The two halves differ in size by at most one.
2L4mid=3 segment=[0, 6]Segment [0, 6] has 7 keys: the middle one, 40, becomes the root of this subtree.
3L4mid=1 segment=[0, 2]Segment [0, 2] has 3 keys: the middle one, 20, becomes the root of this subtree.
4L4mid=0 segment=[0, 0]Segment [0, 0] has 1 key: the middle one, 10, becomes the root of this subtree.
5L2segment=[0, -1]The segment [0, -1] is empty: that child is null.
6L2segment=[1, 0]The segment [1, 0] is empty: that child is null.
7L4mid=2 segment=[2, 2]Segment [2, 2] has 1 key: the middle one, 30, becomes the root of this subtree.
8L2segment=[2, 1]The segment [2, 1] is empty: that child is null.
9L2segment=[3, 2]The segment [3, 2] is empty: that child is null.
10L4mid=5 segment=[4, 6]Segment [4, 6] has 3 keys: the middle one, 60, becomes the root of this subtree.
11L4mid=4 segment=[4, 4]Segment [4, 4] has 1 key: the middle one, 50, becomes the root of this subtree.
12L2segment=[4, 3]The segment [4, 3] is empty: that child is null.
13L2segment=[5, 4]The segment [5, 4] is empty: that child is null.
14L4mid=6 segment=[6, 6]Segment [6, 6] has 1 key: the middle one, 70, becomes the root of this subtree.
15L2segment=[6, 5]The segment [6, 5] is empty: that child is null.
16L2segment=[7, 6]The segment [7, 6] is empty: that child is null.
17L7height=2 minimum height=2Height 2 for 7 keys: the smallest possible height is 2, so this tree is as short as a binary tree can be.

Practice ladder

Now try it yourself

Easy

  • Validate Binary Search Tree (small inputs)
  • Convert Sorted Array to Binary Search Tree

Medium

  • Validate Binary Search Tree
  • Recover Binary Search Tree
  • Construct Binary Search Tree from Preorder Traversal

Advanced

  • Largest BST Subtree
  • Verify Preorder Sequence in Binary Search Tree

Key takeaways

  • Checking a node only against its children is wrong: carry the open range from all ancestors.
  • A binary tree is a BST exactly when its inorder sequence is strictly increasing.
  • Two swapped keys show up as one or two descents; swap the larger of the first with the smaller of the last.
  • Passing an upper bound builds a BST from a preorder sequence in O(n).