25.03Intermediate / Advanced6 topics17 min6 interactive animations

BST queries

Ordered queries on a BST: floor and ceiling, lower and upper bounds, the k-th smallest key, rank, range sums and range traversals.

Learning goals

Find the nearest keys at or around a value with floor, ceiling, lower and higher
Answer k-th smallest and rank with size fields in O(h)
Sum or list the keys of a range while skipping whole subtrees

Prerequisites

The BST invariantBST updates

A hash table answers 'is this key present?'. An ordered structure also answers 'what is the closest key?', 'how many keys are smaller?' and 'which keys lie in this range?', all in O(h).

25.03.1

Floor/ceiling

The **floor** of x is the largest key that is at most x; the **ceiling** is the smallest key that is at least x. Walk down as in a search, and whenever the current key is a *candidate* remember it and look for a better one on the other side. For floor, a key that is too big sends the walk left; a key that fits is a candidate and sends it right.

In the 7-key tree, the “Floor of an absent key” preset gives 60 for 65 and the “Ceiling of an absent key” preset gives 70. For 10 there is no floor (the “No floor exists” preset): every key is bigger, so nothing ever becomes a candidate.

Java

1static Integer floor(Node n, int x) {                // largest key <= x
2    Integer ans = null;
3    while (n != null) {
4        if (n.key == x) return n.key;
5        if (n.key > x) n = n.left;                   // too big: look left
6        else { ans = n.key; n = n.right; }           // a candidate: look right for a closer one
7    }
8    return ans;
9}
10static Integer ceiling(Node n, int x) {              // smallest key >= x
11    Integer ans = null;
12    while (n != null) {
13        if (n.key == x) return n.key;
14        if (n.key < x) n = n.right;
15        else { ans = n.key; n = n.left; }
16    }
17    return ans;
18}

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.03.2

Lower/upper bound

Java's navigable collections name four neighbours: floor (at most), ceiling (at least), lower (strictly less) and higher (strictly greater). The strict ones are the predecessor and the successor of a value that may or may not be in the tree. Other languages call things differently: C++ lower_bound is Java's ceiling and upper_bound is higher. Always check which one a problem means.

The code differs from floor and ceiling only in using < and > instead of <= and >=. In the “Predecessor of a key” preset, the lower neighbour of 50 is 40; in the “Successor is an ancestor” preset the higher neighbour of 40 is 50.

Java

1static Integer lower(Node n, int x) {                // largest key < x
2    Integer ans = null;
3    while (n != null) {
4        if (n.key >= x) n = n.left;
5        else { ans = n.key; n = n.right; }
6    }
7    return ans;
8}
9static Integer higher(Node n, int x) {               // smallest key > x
10    Integer ans = null;
11    while (n != null) {
12        if (n.key <= x) n = n.right;
13        else { ans = n.key; n = n.left; }
14    }
15    return ans;
16}

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.03.3

Kth smallest

To find the **k-th smallest** key, store in every node the size of its subtree. At a node, let left be the size of its left subtree. If k <= left, the answer is in the left subtree. If k == left + 1, this node is it. Otherwise skip the left subtree and this node and look for number k - left - 1 on the right. The walk is O(h). Without size fields, an inorder traversal that stops at the k-th key costs O(h + k).

In the “3rd smallest” preset the sizes shown below the nodes drive the walk: the root has a left subtree of size 3, so the 3rd smallest is in the left subtree. At node 30 (left size 1) the key 3 is past 1 + 1 = 2 keys, so skip 30's left subtree and 30 itself and look for number 1 on the right: that is 40.

Java

1static int size(Node n) { return n == null ? 0 : n.size; }
2
3static int kthSmallest(Node n, int k) {              // 1-based; every node keeps its subtree size
4    while (n != null) {
5        int left = size(n.left);
6        if (k <= left) n = n.left;
7        else if (k == left + 1) return n.key;
8        else { k -= left + 1; n = n.right; }
9    }
10    throw new NoSuchElementException();
11}

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.03.4

Rank

The **rank** of x is the number of keys smaller than x, the inverse of k-th smallest. Walk down as for a search; whenever the walk goes right, everything in the left subtree and the node itself is smaller than x, so add size(left) + 1. Going left adds nothing.

In the “Rank of 65” preset the rank is 5: the keys 20, 30, 40, 50 and 60 are smaller. The sizes shown under the nodes are what make each step O(1). Rank and k-th smallest together make an **order-statistic tree**.

Java

1static int rank(Node n, int x) {                     // how many keys are < x
2    int r = 0;
3    while (n != null) {
4        if (x <= n.key) n = n.left;
5        else { r += size(n.left) + 1; n = n.right; }
6    }
7    return r;
8}
9static int size(Node n) { return n == null ? 0 : n.size; }

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.03.5

Range sum

The sum of the keys in [lo, hi] is an inorder traversal that **prunes**: skip the left subtree when the current key is at most lo (everything there is smaller than lo) and skip the right subtree when the current key is at least hi. Only the nodes on the two boundary paths and the nodes inside the range are visited, so the cost is O(h + k) for k keys in the range, instead of O(n).

On the 7-key tree the “Range sum [35, 65]” preset sums 40 + 50 + 60 = 150 and visits 5 of the 7 nodes; the animation shades the skipped subtrees.

Java

1static int rangeSum(Node n, int lo, int hi) {
2    if (n == null) return 0;
3    int sum = 0;
4    if (n.key > lo) sum += rangeSum(n.left, lo, hi);      // the left subtree may hold keys >= lo
5    if (lo <= n.key && n.key <= hi) sum += n.key;
6    if (n.key < hi) sum += rangeSum(n.right, lo, hi);     // the right subtree may hold keys <= hi
7    return sum;
8}

Best

O(h)

Average

O(log n + k)

Worst

O(n)

Space

O(h)

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.03.6

Range traversal

Collecting the keys in [lo, hi] uses the same pruned traversal in inorder, so the output is already sorted. This is what subMap and subSet views do in TreeMap and TreeSet. The total cost is O(h + k): descend to the boundary once, then walk the k results.

The difference from sorting the whole data: with a BST the first result is found in O(h) and the traversal can stop early, which fits 'list the next 10 keys after x' questions.

Java

1static void range(Node n, int lo, int hi, List<Integer> out) {
2    if (n == null) return;
3    if (n.key > lo) range(n.left, lo, hi, out);
4    if (lo <= n.key && n.key <= hi) out.add(n.key);       // inorder position: results come out sorted
5    if (n.key < hi) range(n.right, lo, hi, out);
6}

Best

O(h)

Average

O(log n + k)

Worst

O(n)

Space

O(h)

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

Range Sum of BST
Closest Binary Search Tree Value

Medium

Kth Smallest Element in a BST
Count of Smaller Numbers After Self

Advanced

Count of Range Sum
Count of Smaller Numbers After Self (with a BST)

Key takeaways

Floor, ceiling, lower and higher walk down once and remember the last candidate.
C++ lower_bound is Java's ceiling and upper_bound is higher: check the naming.
Subtree sizes give k-th smallest and rank in O(h).
Range queries prune whole subtrees outside [lo, hi] and cost O(h + k).