25.01Intermediate / Advanced6 topics16 min6 interactive animations

BST invariant

The binary search tree rule and what follows from it: the ordering invariant, duplicate policies, search, minimum and maximum, successor and predecessor.

Learning goals

State the BST invariant for whole subtrees, not just for children
Choose and implement a duplicate-key policy
Search, find the minimum and maximum, and walk to successors and predecessors in O(h)
Explain why the inorder sequence of a BST is sorted

Prerequisites

Tree fundamentals and traversalBinary search

A binary search tree keeps its keys ordered so that every comparison discards a whole subtree: binary search on a linked structure that supports insertion and deletion.

25.01.1

Ordering rule

A **binary search tree** (BST) is a binary tree in which, for every node, all keys in its **left subtree** are smaller than the node's key and all keys in its **right subtree** are larger. The rule is about whole subtrees: a node's left child being smaller is not enough if a node deeper down breaks the ordering with an ancestor.

Because of the rule, an inorder traversal visits the keys in increasing order, and any search can discard one subtree per comparison. Run the “In-order traversal” preset: the output [20, 30, 40, 50, 60, 70, 80] is sorted, which is how the animation states the rule.

Java

1static class Node {
2    int key;
3    Node left, right;
4    Node(int key) { this.key = key; }
5}
6static boolean contains(Node n, int key) {
7    if (n == null) return false;                     // fell off the tree: the key is absent
8    if (key == n.key) return true;
9    return key < n.key ? contains(n.left, key) : contains(n.right, key);   // discard one whole subtree
10}

Binary search tree: insert, search, delete and in-order traversal

Interactive · edit the input

Setup

An empty tree. Rule: every key in a node's left subtree is smaller, every key in its right subtree is larger.

Step 1 / 13

Java

1class Bst {
2    private static class Node { int key; Node left, right; Node(int k) { key = k; } }
3    private Node root;
4    void insert(int key) { root = insert(root, key); }
5    private Node insert(Node n, int key) {
6        if (n == null) return new Node(key);                      // found the empty spot
7        if (key < n.key) n.left = insert(n.left, key);
8        else if (key > n.key) n.right = insert(n.right, key);     // equal keys are ignored
9        return n;
10    }
11    boolean contains(int key) {
12        Node n = root;
13        while (n != null) {
14            if (key == n.key) return true;
15            n = key < n.key ? n.left : n.right;                    // discard one whole subtree
16        }
17        return false;
18    }
19    void delete(int key) { root = delete(root, key); }
20    private Node delete(Node n, int key) {
21        if (n == null) return null;                               // key is not in the tree
22        if (key < n.key) n.left = delete(n.left, key);
23        else if (key > n.key) n.right = delete(n.right, key);
24        else {
25            if (n.left == null) return n.right;                    // zero or one child: splice the node out
26            if (n.right == null) return n.left;
27            Node s = n.right; while (s.left != null) s = s.left;   // two children: in-order successor
28            n.key = s.key;                                         // copy its key up
29            n.right = delete(n.right, s.key);                      // then remove the successor
30        }
31        return n;
32    }
33    void inorder(Node n, List<Integer> out) {
34        if (n == null) return;
35        inorder(n.left, out); out.add(n.key); inorder(n.right, out);   // left, node, right: sorted order
36    }
37}

Live state

0 comparisons

size

No condition evaluated on this step

Execution trace (dry run table)Show 13 steps

Step	Line	State	What happens
1	L3	size=0	An empty tree. Rule: every key in a node's left subtree is smaller, every key in its right subtree is larger.
2	L6	inserted=50 size=1	Insert 50: the tree is empty, so it becomes the root.
3	L7	inserted=30 size=2	Insert 30: compared with 50, it ends as the left child of 50.
4	L8	inserted=70 size=3	Insert 70: compared with 50, it ends as the right child of 50.
5	L7	inserted=20 size=4	Insert 20: compared with 50 → 30, it ends as the left child of 30.
6	L8	inserted=40 size=5	Insert 40: compared with 50 → 30, it ends as the right child of 30.
7	L7	inserted=60 size=6	Insert 60: compared with 50 → 70, it ends as the left child of 70.
8	L8	inserted=80 size=7	Insert 80: compared with 50 → 70, it ends as the right child of 70.
9	L12	key=60 size=7	Search for 60: start at the root.
10	L14	key=60 node=50 steps=1	60 > 50: go right; the whole left subtree is ruled out.
11	L14	key=60 node=70 steps=2	60 < 70: go left; the whole right subtree is ruled out.
12	L14	key=60 node=60 steps=3	60 == 60: found after 3 comparisons.
13	L14	return=true steps=3	contains(60) = true in 3 steps; the tree has 7 keys, so most of them were never looked at.

25.01.2

Duplicates policy

What should insert do when the key is already present? Four common policies. **Ignore**: a set semantics, used in the animations here. **Count**: keep a count in the node, which turns the tree into a multiset. **Replace**: overwrite the stored value, as a map's put does. **Allow on one side**: say, equal keys go to the right subtree, which keeps duplicates as separate nodes but weakens the invariant to left < node <= right.

Pick one and state it, since validation, search and deletion all depend on it. The strict form (left < node < right) is simplest to reason about and to validate; code that allows duplicates on one side must use the matching comparison everywhere.

Java

1// count policy: a multiset
2static class Node {
3    int key, count = 1;
4    Node left, right;
5    Node(int key) { this.key = key; }
6}
7static Node insert(Node n, int key) {
8    if (n == null) return new Node(key);
9    if (key < n.key) n.left = insert(n.left, key);
10    else if (key > n.key) n.right = insert(n.right, key);
11    else n.count++;                                  // equal key: one more copy, no new node
12    return n;
13}

Binary search tree: insert, search, delete and in-order traversal

Interactive · edit the input

Setup

An empty tree. Rule: every key in a node's left subtree is smaller, every key in its right subtree is larger.

Step 1 / 13

Java

1class Bst {
2    private static class Node { int key; Node left, right; Node(int k) { key = k; } }
3    private Node root;
4    void insert(int key) { root = insert(root, key); }
5    private Node insert(Node n, int key) {
6        if (n == null) return new Node(key);                      // found the empty spot
7        if (key < n.key) n.left = insert(n.left, key);
8        else if (key > n.key) n.right = insert(n.right, key);     // equal keys are ignored
9        return n;
10    }
11    boolean contains(int key) {
12        Node n = root;
13        while (n != null) {
14            if (key == n.key) return true;
15            n = key < n.key ? n.left : n.right;                    // discard one whole subtree
16        }
17        return false;
18    }
19    void delete(int key) { root = delete(root, key); }
20    private Node delete(Node n, int key) {
21        if (n == null) return null;                               // key is not in the tree
22        if (key < n.key) n.left = delete(n.left, key);
23        else if (key > n.key) n.right = delete(n.right, key);
24        else {
25            if (n.left == null) return n.right;                    // zero or one child: splice the node out
26            if (n.right == null) return n.left;
27            Node s = n.right; while (s.left != null) s = s.left;   // two children: in-order successor
28            n.key = s.key;                                         // copy its key up
29            n.right = delete(n.right, s.key);                      // then remove the successor
30        }
31        return n;
32    }
33    void inorder(Node n, List<Integer> out) {
34        if (n == null) return;
35        inorder(n.left, out); out.add(n.key); inorder(n.right, out);   // left, node, right: sorted order
36    }
37}

Live state

0 comparisons

size

No condition evaluated on this step

Execution trace (dry run table)Show 13 steps

Step	Line	State	What happens
1	L3	size=0	An empty tree. Rule: every key in a node's left subtree is smaller, every key in its right subtree is larger.
2	L6	inserted=50 size=1	Insert 50: the tree is empty, so it becomes the root.
3	L7	inserted=30 size=2	Insert 30: compared with 50, it ends as the left child of 50.
4	L8	inserted=70 size=3	Insert 70: compared with 50, it ends as the right child of 50.
5	L7	inserted=20 size=4	Insert 20: compared with 50 → 30, it ends as the left child of 30.
6	L8	inserted=40 size=5	Insert 40: compared with 50 → 30, it ends as the right child of 30.
7	L7	inserted=60 size=6	Insert 60: compared with 50 → 70, it ends as the left child of 70.
8	L8	inserted=80 size=7	Insert 80: compared with 50 → 70, it ends as the right child of 70.
9	L12	key=60 size=7	Search for 60: start at the root.
10	L14	key=60 node=50 steps=1	60 > 50: go right; the whole left subtree is ruled out.
11	L14	key=60 node=70 steps=2	60 < 70: go left; the whole right subtree is ruled out.
12	L14	key=60 node=60 steps=3	60 == 60: found after 3 comparisons.
13	L14	return=true steps=3	contains(60) = true in 3 steps; the tree has 7 keys, so most of them were never looked at.

25.01.3

Search

Search compares the target with the current node and moves left or right, one comparison per level, until it finds the key or falls off the tree. The cost is O(h): the number of comparisons is at most the height plus one. In the “Search (found)” preset, contains(60) takes 3 steps in a 7-key tree; in the “Search (absent)” preset, 65 falls off the tree after 3 comparisons.

The “Sorted input (a chain)” preset shows the danger: the same 5 keys inserted in increasing order form a chain, and finding 50 takes 5 steps. A BST is only as fast as it is short.

Java

1static boolean containsIter(Node n, int key) {
2    while (n != null) {
3        if (key == n.key) return true;
4        n = key < n.key ? n.left : n.right;          // no recursion needed
5    }
6    return false;
7}

Best

O(1)

Average

O(log n)

Worst

O(n)

Space

O(1)

Binary search tree: insert, search, delete and in-order traversal

Interactive · edit the input

Setup

An empty tree. Rule: every key in a node's left subtree is smaller, every key in its right subtree is larger.

Step 1 / 13

Java

1class Bst {
2    private static class Node { int key; Node left, right; Node(int k) { key = k; } }
3    private Node root;
4    void insert(int key) { root = insert(root, key); }
5    private Node insert(Node n, int key) {
6        if (n == null) return new Node(key);                      // found the empty spot
7        if (key < n.key) n.left = insert(n.left, key);
8        else if (key > n.key) n.right = insert(n.right, key);     // equal keys are ignored
9        return n;
10    }
11    boolean contains(int key) {
12        Node n = root;
13        while (n != null) {
14            if (key == n.key) return true;
15            n = key < n.key ? n.left : n.right;                    // discard one whole subtree
16        }
17        return false;
18    }
19    void delete(int key) { root = delete(root, key); }
20    private Node delete(Node n, int key) {
21        if (n == null) return null;                               // key is not in the tree
22        if (key < n.key) n.left = delete(n.left, key);
23        else if (key > n.key) n.right = delete(n.right, key);
24        else {
25            if (n.left == null) return n.right;                    // zero or one child: splice the node out
26            if (n.right == null) return n.left;
27            Node s = n.right; while (s.left != null) s = s.left;   // two children: in-order successor
28            n.key = s.key;                                         // copy its key up
29            n.right = delete(n.right, s.key);                      // then remove the successor
30        }
31        return n;
32    }
33    void inorder(Node n, List<Integer> out) {
34        if (n == null) return;
35        inorder(n.left, out); out.add(n.key); inorder(n.right, out);   // left, node, right: sorted order
36    }
37}

Live state

0 comparisons

size

No condition evaluated on this step

Execution trace (dry run table)Show 13 steps

Step	Line	State	What happens
1	L3	size=0	An empty tree. Rule: every key in a node's left subtree is smaller, every key in its right subtree is larger.
2	L6	inserted=50 size=1	Insert 50: the tree is empty, so it becomes the root.
3	L7	inserted=30 size=2	Insert 30: compared with 50, it ends as the left child of 50.
4	L8	inserted=70 size=3	Insert 70: compared with 50, it ends as the right child of 50.
5	L7	inserted=20 size=4	Insert 20: compared with 50 → 30, it ends as the left child of 30.
6	L8	inserted=40 size=5	Insert 40: compared with 50 → 30, it ends as the right child of 30.
7	L7	inserted=60 size=6	Insert 60: compared with 50 → 70, it ends as the left child of 70.
8	L8	inserted=80 size=7	Insert 80: compared with 50 → 70, it ends as the right child of 70.
9	L12	key=60 size=7	Search for 60: start at the root.
10	L14	key=60 node=50 steps=1	60 > 50: go right; the whole left subtree is ruled out.
11	L14	key=60 node=70 steps=2	60 < 70: go left; the whole right subtree is ruled out.
12	L14	key=60 node=60 steps=3	60 == 60: found after 3 comparisons.
13	L14	return=true steps=3	contains(60) = true in 3 steps; the tree has 7 keys, so most of them were never looked at.

25.01.4

Minimum/maximum

The **minimum** key is at the end of the left spine: keep going left until there is no left child. The **maximum** is the end of the right spine. Both take O(h) and need no comparisons at all, since the ordering rule already says where the extremes are.

The two functions also find the extremes of any subtree, which the successor and deletion code reuse. The animation's query mode shows the walk for both (choose the “Minimum” or “Maximum” query).

Java

1static Integer minimum(Node n) {
2    if (n == null) return null;
3    while (n.left != null) n = n.left;               // the leftmost node
4    return n.key;
5}
6static Integer maximum(Node n) {
7    if (n == null) return null;
8    while (n.right != null) n = n.right;             // the rightmost node
9    return n.key;
10}

Best

O(1)

Average

O(log n)

Worst

O(n)

Space

O(1)

BST queries: floor, ceiling, predecessor, successor, k-th smallest, rank, range sum

Interactive · edit the input

binary search tree · 7 nodes

Current nodeVisited on the way downBest candidate so farAnswerSubtree skippedCounted

Setup

A BST of 7 keys, inorder [20, 30, 40, 50, 60, 70, 80]. Floor (largest key <= x).

Step 1 / 5

Java

1static class Node { int key, size = 1; Node left, right; Node(int k) { key = k; } }
2static Integer floor(Node n, int x) {            // largest key <= x
3    Integer ans = null;
4    while (n != null) {
5        if (n.key == x) return n.key;
6        if (n.key > x) n = n.left;               // too big: look left
7        else { ans = n.key; n = n.right; }       // a candidate: look right for a closer one
8    }
9    return ans;
10}
11static Integer ceiling(Node n, int x) {          // smallest key >= x
12    Integer ans = null;
13    while (n != null) {
14        if (n.key == x) return n.key;
15        if (n.key < x) n = n.right;
16        else { ans = n.key; n = n.left; }
17    }
18    return ans;
19}
20static Integer lower(Node n, int x) {            // largest key < x: the predecessor
21    Integer ans = null;
22    while (n != null) {
23        if (n.key >= x) n = n.left;
24        else { ans = n.key; n = n.right; }
25    }
26    return ans;
27}
28static Integer higher(Node n, int x) {           // smallest key > x: the successor
29    Integer ans = null;
30    while (n != null) {
31        if (n.key <= x) n = n.right;
32        else { ans = n.key; n = n.left; }
33    }
34    return ans;
35}
36static int size(Node n) { return n == null ? 0 : n.size; }
37static int kthSmallest(Node n, int k) {          // 1-based; needs the size fields
38    while (n != null) {
39        int left = size(n.left);
40        if (k <= left) n = n.left;
41        else if (k == left + 1) return n.key;
42        else { k -= left + 1; n = n.right; }
43    }
44    throw new NoSuchElementException();
45}
46static int rank(Node n, int x) {                 // how many keys are < x
47    int r = 0;
48    while (n != null) {
49        if (x <= n.key) n = n.left;
50        else { r += size(n.left) + 1; n = n.right; }
51    }
52    return r;
53}
54static int rangeSum(Node n, int lo, int hi) {
55    if (n == null) return 0;
56    int sum = 0;
57    if (n.key > lo) sum += rangeSum(n.left, lo, hi);      // the left subtree may hold keys >= lo
58    if (lo <= n.key && n.key <= hi) sum += n.key;
59    if (n.key < hi) sum += rangeSum(n.right, lo, hi);     // the right subtree may hold keys <= hi
60    return sum;
61}
62static Integer minimum(Node n) { if (n == null) return null; while (n.left != null) n = n.left; return n.key; }
63static Integer maximum(Node n) { if (n == null) return null; while (n.right != null) n = n.right; return n.key; }

Live state

0 nodes visited

keys

height

No condition evaluated on this step

Execution trace (dry run table)Show 5 steps

Step	Line	State	What happens
1	L2	keys=7 height=2	A BST of 7 keys, inorder [20, 30, 40, 50, 60, 70, 80]. Floor (largest key <= x).
2	L7	x=65	50 <= 65: 50 is a candidate for the floor; a larger one can only be in its right subtree.
3	L6	x=65	70 > 65: too big to be the floor, so discard it and its whole right subtree and go left.
4	L7	x=65	60 <= 65: 60 is a candidate for the floor; a larger one can only be in its right subtree.
5	L4	x=65 result=60	The floor of 65 is 60.

25.01.5

Successor

The **successor** of a key is the smallest key greater than it: the next node in inorder. Two cases. If the node has a right subtree, the successor is the **minimum of that right subtree**. If not, it is the **lowest ancestor whose left subtree contains the node**, the last ancestor at which the path turned left.

In the tree built from 50, 30, 70, 20, 40, 60, 80 the “Successor: smallest key of the right subtree” preset finds 60 for 50 (the minimum of 50's right subtree). The “Successor is an ancestor” preset finds 50 for 40, because 40 has no right child and 50 is the last ancestor from which the path went left. The maximum, 80, has no successor.

Searching from the root solves both cases at once: walk down toward the key, and remember the last node where you went left.

Java

1static Integer successor(Node n, int key) {          // smallest key > key, or null
2    Integer ans = null;
3    while (n != null) {
4        if (n.key <= key) n = n.right;               // too small: the answer is in the right subtree
5        else { ans = n.key; n = n.left; }            // a candidate; look for a closer one on the left
6    }
7    return ans;
8}

Best

O(1)

Average

O(log n)

Worst

O(n)

Space

O(1)

BST queries: floor, ceiling, predecessor, successor, k-th smallest, rank, range sum

Interactive · edit the input

binary search tree · 7 nodes

Current nodeVisited on the way downBest candidate so farAnswerSubtree skippedCounted

Setup

A BST of 7 keys, inorder [20, 30, 40, 50, 60, 70, 80]. Floor (largest key <= x).

Step 1 / 5

Java

1static class Node { int key, size = 1; Node left, right; Node(int k) { key = k; } }
2static Integer floor(Node n, int x) {            // largest key <= x
3    Integer ans = null;
4    while (n != null) {
5        if (n.key == x) return n.key;
6        if (n.key > x) n = n.left;               // too big: look left
7        else { ans = n.key; n = n.right; }       // a candidate: look right for a closer one
8    }
9    return ans;
10}
11static Integer ceiling(Node n, int x) {          // smallest key >= x
12    Integer ans = null;
13    while (n != null) {
14        if (n.key == x) return n.key;
15        if (n.key < x) n = n.right;
16        else { ans = n.key; n = n.left; }
17    }
18    return ans;
19}
20static Integer lower(Node n, int x) {            // largest key < x: the predecessor
21    Integer ans = null;
22    while (n != null) {
23        if (n.key >= x) n = n.left;
24        else { ans = n.key; n = n.right; }
25    }
26    return ans;
27}
28static Integer higher(Node n, int x) {           // smallest key > x: the successor
29    Integer ans = null;
30    while (n != null) {
31        if (n.key <= x) n = n.right;
32        else { ans = n.key; n = n.left; }
33    }
34    return ans;
35}
36static int size(Node n) { return n == null ? 0 : n.size; }
37static int kthSmallest(Node n, int k) {          // 1-based; needs the size fields
38    while (n != null) {
39        int left = size(n.left);
40        if (k <= left) n = n.left;
41        else if (k == left + 1) return n.key;
42        else { k -= left + 1; n = n.right; }
43    }
44    throw new NoSuchElementException();
45}
46static int rank(Node n, int x) {                 // how many keys are < x
47    int r = 0;
48    while (n != null) {
49        if (x <= n.key) n = n.left;
50        else { r += size(n.left) + 1; n = n.right; }
51    }
52    return r;
53}
54static int rangeSum(Node n, int lo, int hi) {
55    if (n == null) return 0;
56    int sum = 0;
57    if (n.key > lo) sum += rangeSum(n.left, lo, hi);      // the left subtree may hold keys >= lo
58    if (lo <= n.key && n.key <= hi) sum += n.key;
59    if (n.key < hi) sum += rangeSum(n.right, lo, hi);     // the right subtree may hold keys <= hi
60    return sum;
61}
62static Integer minimum(Node n) { if (n == null) return null; while (n.left != null) n = n.left; return n.key; }
63static Integer maximum(Node n) { if (n == null) return null; while (n.right != null) n = n.right; return n.key; }

Live state

0 nodes visited

keys

height

No condition evaluated on this step

Execution trace (dry run table)Show 5 steps

Step	Line	State	What happens
1	L2	keys=7 height=2	A BST of 7 keys, inorder [20, 30, 40, 50, 60, 70, 80]. Floor (largest key <= x).
2	L7	x=65	50 <= 65: 50 is a candidate for the floor; a larger one can only be in its right subtree.
3	L6	x=65	70 > 65: too big to be the floor, so discard it and its whole right subtree and go left.
4	L7	x=65	60 <= 65: 60 is a candidate for the floor; a larger one can only be in its right subtree.
5	L4	x=65 result=60	The floor of 65 is 60.

25.01.6

Predecessor

The **predecessor** is the mirror image: the largest key smaller than the given one. With a left subtree it is the maximum of that subtree; without one, it is the lowest ancestor from which the path turned right. In the “Predecessor of a key” preset, 40 is the predecessor of 50, the maximum of 50's left subtree.

Successor and predecessor let you step through the keys in order without recursion, which is how TreeMap iterators work, and they give the neighbours needed to delete a node with two children.

Java

1static Integer predecessor(Node n, int key) {        // largest key < key, or null
2    Integer ans = null;
3    while (n != null) {
4        if (n.key >= key) n = n.left;
5        else { ans = n.key; n = n.right; }
6    }
7    return ans;
8}

Best

O(1)

Average

O(log n)

Worst

O(n)

Space

O(1)

BST queries: floor, ceiling, predecessor, successor, k-th smallest, rank, range sum

Interactive · edit the input

binary search tree · 7 nodes

Current nodeVisited on the way downBest candidate so farAnswerSubtree skippedCounted

Setup

A BST of 7 keys, inorder [20, 30, 40, 50, 60, 70, 80]. Floor (largest key <= x).

Step 1 / 5

Java

1static class Node { int key, size = 1; Node left, right; Node(int k) { key = k; } }
2static Integer floor(Node n, int x) {            // largest key <= x
3    Integer ans = null;
4    while (n != null) {
5        if (n.key == x) return n.key;
6        if (n.key > x) n = n.left;               // too big: look left
7        else { ans = n.key; n = n.right; }       // a candidate: look right for a closer one
8    }
9    return ans;
10}
11static Integer ceiling(Node n, int x) {          // smallest key >= x
12    Integer ans = null;
13    while (n != null) {
14        if (n.key == x) return n.key;
15        if (n.key < x) n = n.right;
16        else { ans = n.key; n = n.left; }
17    }
18    return ans;
19}
20static Integer lower(Node n, int x) {            // largest key < x: the predecessor
21    Integer ans = null;
22    while (n != null) {
23        if (n.key >= x) n = n.left;
24        else { ans = n.key; n = n.right; }
25    }
26    return ans;
27}
28static Integer higher(Node n, int x) {           // smallest key > x: the successor
29    Integer ans = null;
30    while (n != null) {
31        if (n.key <= x) n = n.right;
32        else { ans = n.key; n = n.left; }
33    }
34    return ans;
35}
36static int size(Node n) { return n == null ? 0 : n.size; }
37static int kthSmallest(Node n, int k) {          // 1-based; needs the size fields
38    while (n != null) {
39        int left = size(n.left);
40        if (k <= left) n = n.left;
41        else if (k == left + 1) return n.key;
42        else { k -= left + 1; n = n.right; }
43    }
44    throw new NoSuchElementException();
45}
46static int rank(Node n, int x) {                 // how many keys are < x
47    int r = 0;
48    while (n != null) {
49        if (x <= n.key) n = n.left;
50        else { r += size(n.left) + 1; n = n.right; }
51    }
52    return r;
53}
54static int rangeSum(Node n, int lo, int hi) {
55    if (n == null) return 0;
56    int sum = 0;
57    if (n.key > lo) sum += rangeSum(n.left, lo, hi);      // the left subtree may hold keys >= lo
58    if (lo <= n.key && n.key <= hi) sum += n.key;
59    if (n.key < hi) sum += rangeSum(n.right, lo, hi);     // the right subtree may hold keys <= hi
60    return sum;
61}
62static Integer minimum(Node n) { if (n == null) return null; while (n.left != null) n = n.left; return n.key; }
63static Integer maximum(Node n) { if (n == null) return null; while (n.right != null) n = n.right; return n.key; }

Live state

0 nodes visited

keys

height

No condition evaluated on this step

Execution trace (dry run table)Show 5 steps

Step	Line	State	What happens
1	L2	keys=7 height=2	A BST of 7 keys, inorder [20, 30, 40, 50, 60, 70, 80]. Floor (largest key <= x).
2	L7	x=65	50 <= 65: 50 is a candidate for the floor; a larger one can only be in its right subtree.
3	L6	x=65	70 > 65: too big to be the floor, so discard it and its whole right subtree and go left.
4	L7	x=65	60 <= 65: 60 is a candidate for the floor; a larger one can only be in its right subtree.
5	L4	x=65 result=60	The floor of 65 is 60.

Practice ladder

Now try it yourself

Easy

Search in a Binary Search Tree
Minimum Absolute Difference in BST

Medium

Inorder Successor in BST
Insert into a Binary Search Tree

Advanced

Closest Binary Search Tree Value II
BST Iterator

Key takeaways

In a BST every key in a node's left subtree is smaller and every key in its right subtree is larger.
Inorder traversal of a BST is sorted; search discards one subtree per comparison, in O(h).
Choose a duplicate policy (ignore, count, replace, one side) and apply it everywhere.
Minimum and maximum follow the left and right spines.
The successor is the right subtree's minimum, or else the last ancestor where the path turned left.