25.05Intermediate / Advanced5 topics14 min4 interactive animations

BST construction

How BSTs come into being and what their shape costs: balanced trees from sorted data, balanced building, degenerate trees, the effect of height and random insertion order.

Learning goals

Build a minimum-height BST from sorted data
Recognise how insertion order decides the shape
Quantify the cost of a degenerate tree
Quote the typical height of a tree built from random insertions

Prerequisites

BST updates

Every BST operation costs O(h). The shape of the tree is decided by the order in which keys arrive, so it pays to know which orders are good and which are terrible.

25.05.1

Sorted array to BST

From sorted, distinct keys you can build the **shortest possible** BST in O(n): make the middle key the root, and build the left and right subtrees from the two halves. The halves differ in size by at most one, which keeps every subtree balanced.

The “Sorted array, balanced” preset turns 7 keys into a perfect tree of height 2. With 6 keys (the “Even number of keys” preset) the height is still 2: one half is one key larger than the other.

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}

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(log n) recursion

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

Interactive · edit the input

sorted keys

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

No condition evaluated on this step

Execution trace (dry run table)Show 17 steps

Step	Line	State	What happens
1	L1	keys=7	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.
2	L4	mid=3 segment=[0, 6]	Segment [0, 6] has 7 keys: the middle one, 40, becomes the root of this subtree.
3	L4	mid=1 segment=[0, 2]	Segment [0, 2] has 3 keys: the middle one, 20, becomes the root of this subtree.
4	L4	mid=0 segment=[0, 0]	Segment [0, 0] has 1 key: the middle one, 10, becomes the root of this subtree.
5	L2	segment=[0, -1]	The segment [0, -1] is empty: that child is null.
6	L2	segment=[1, 0]	The segment [1, 0] is empty: that child is null.
7	L4	mid=2 segment=[2, 2]	Segment [2, 2] has 1 key: the middle one, 30, becomes the root of this subtree.
8	L2	segment=[2, 1]	The segment [2, 1] is empty: that child is null.
9	L2	segment=[3, 2]	The segment [3, 2] is empty: that child is null.
10	L4	mid=5 segment=[4, 6]	Segment [4, 6] has 3 keys: the middle one, 60, becomes the root of this subtree.
11	L4	mid=4 segment=[4, 4]	Segment [4, 4] has 1 key: the middle one, 50, becomes the root of this subtree.
12	L2	segment=[4, 3]	The segment [4, 3] is empty: that child is null.
13	L2	segment=[5, 4]	The segment [5, 4] is empty: that child is null.
14	L4	mid=6 segment=[6, 6]	Segment [6, 6] has 1 key: the middle one, 70, becomes the root of this subtree.
15	L2	segment=[6, 5]	The segment [6, 5] is empty: that child is null.
16	L2	segment=[7, 6]	The segment [7, 6] is empty: that child is null.
17	L7	height=2 minimum height=2	Height 2 for 7 keys: the smallest possible height is 2, so this tree is as short as a binary tree can be.

25.05.2

Balanced build

'Balanced' here means the height of the two subtrees of every node differ by at most 1, and the middle-key construction guarantees it, with height ⌊log2 n⌋, the minimum for n keys. When n is even, either middle key works: (lo + hi) / 2 picks the lower and (lo + hi + 1) / 2 the upper; both give valid trees of the same height.

Write the midpoint as lo + (hi - lo) / 2 or (lo + hi) >>> 1; the plain (lo + hi) / 2 overflows for very large indexes (the same bug as in binary search). The recursion depth is only the height, about log n, so no stack concerns arise.

Java

1static int heightOf(TreeNode n) { return n == null ? -1 : 1 + Math.max(heightOf(n.left), heightOf(n.right)); }
2
3// both middles give a minimum-height tree
4static TreeNode build(int[] a, int lo, int hi, boolean upperMiddle) {
5    if (lo > hi) return null;
6    int mid = upperMiddle ? (lo + hi + 1) >>> 1 : (lo + hi) >>> 1;
7    TreeNode n = new TreeNode(a[mid]);
8    n.left = build(a, lo, mid - 1, upperMiddle);
9    n.right = build(a, mid + 1, hi, upperMiddle);
10    return n;
11}

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

Interactive · edit the input

sorted keys

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

No condition evaluated on this step

Execution trace (dry run table)Show 17 steps

Step	Line	State	What happens
1	L1	keys=7	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.
2	L4	mid=3 segment=[0, 6]	Segment [0, 6] has 7 keys: the middle one, 40, becomes the root of this subtree.
3	L4	mid=1 segment=[0, 2]	Segment [0, 2] has 3 keys: the middle one, 20, becomes the root of this subtree.
4	L4	mid=0 segment=[0, 0]	Segment [0, 0] has 1 key: the middle one, 10, becomes the root of this subtree.
5	L2	segment=[0, -1]	The segment [0, -1] is empty: that child is null.
6	L2	segment=[1, 0]	The segment [1, 0] is empty: that child is null.
7	L4	mid=2 segment=[2, 2]	Segment [2, 2] has 1 key: the middle one, 30, becomes the root of this subtree.
8	L2	segment=[2, 1]	The segment [2, 1] is empty: that child is null.
9	L2	segment=[3, 2]	The segment [3, 2] is empty: that child is null.
10	L4	mid=5 segment=[4, 6]	Segment [4, 6] has 3 keys: the middle one, 60, becomes the root of this subtree.
11	L4	mid=4 segment=[4, 4]	Segment [4, 4] has 1 key: the middle one, 50, becomes the root of this subtree.
12	L2	segment=[4, 3]	The segment [4, 3] is empty: that child is null.
13	L2	segment=[5, 4]	The segment [5, 4] is empty: that child is null.
14	L4	mid=6 segment=[6, 6]	Segment [6, 6] has 1 key: the middle one, 70, becomes the root of this subtree.
15	L2	segment=[6, 5]	The segment [6, 5] is empty: that child is null.
16	L2	segment=[7, 6]	The segment [7, 6] is empty: that child is null.
17	L7	height=2 minimum height=2	Height 2 for 7 keys: the smallest possible height is 2, so this tree is as short as a binary tree can be.

25.05.3

Degenerate BST

Insert the keys in sorted order and every new key is larger than all that came before, so it always goes to the right of the last one: the tree is a **chain**, effectively a linked list, with height n - 1. Every operation then costs O(n).

The “Insertion in sorted order: a chain” preset gives height 6 for 7 keys, where a balanced tree has height 2. Reverse-sorted input gives the mirror image, a left chain. Data that arrives nearly sorted (timestamps, auto-incremented IDs) is the common real case, which is why plain BSTs are rarely used as they are.

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

Interactive · edit the input

sorted keys

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

No condition evaluated on this step

Execution trace (dry run table)Show 17 steps

Step	Line	State	What happens
1	L1	keys=7	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.
2	L4	mid=3 segment=[0, 6]	Segment [0, 6] has 7 keys: the middle one, 40, becomes the root of this subtree.
3	L4	mid=1 segment=[0, 2]	Segment [0, 2] has 3 keys: the middle one, 20, becomes the root of this subtree.
4	L4	mid=0 segment=[0, 0]	Segment [0, 0] has 1 key: the middle one, 10, becomes the root of this subtree.
5	L2	segment=[0, -1]	The segment [0, -1] is empty: that child is null.
6	L2	segment=[1, 0]	The segment [1, 0] is empty: that child is null.
7	L4	mid=2 segment=[2, 2]	Segment [2, 2] has 1 key: the middle one, 30, becomes the root of this subtree.
8	L2	segment=[2, 1]	The segment [2, 1] is empty: that child is null.
9	L2	segment=[3, 2]	The segment [3, 2] is empty: that child is null.
10	L4	mid=5 segment=[4, 6]	Segment [4, 6] has 3 keys: the middle one, 60, becomes the root of this subtree.
11	L4	mid=4 segment=[4, 4]	Segment [4, 4] has 1 key: the middle one, 50, becomes the root of this subtree.
12	L2	segment=[4, 3]	The segment [4, 3] is empty: that child is null.
13	L2	segment=[5, 4]	The segment [5, 4] is empty: that child is null.
14	L4	mid=6 segment=[6, 6]	Segment [6, 6] has 1 key: the middle one, 70, becomes the root of this subtree.
15	L2	segment=[6, 5]	The segment [6, 5] is empty: that child is null.
16	L2	segment=[7, 6]	The segment [7, 6] is empty: that child is null.
17	L7	height=2 minimum height=2	Height 2 for 7 keys: the smallest possible height is 2, so this tree is as short as a binary tree can be.

25.05.4

Height effects

The same 7 keys give very different trees depending on arrival order, and the height is the cost of every search. The animation's three insertion presets show it.

The order 40, 20, 60, 10, 30, 50, 70 gives a perfect tree of height 2 (the “Insertion in a balanced order” preset). The order 40, 10, 30, 50, 20, 60, 70 gives height 3 (“Insertion in a mixed order”). The increasing order 10 to 70 gives height 6. A search costs at most height + 1 comparisons, so these trees need at most 3, 4 and 7.

Insertion order of 7 keys	Height	Most comparisons for a search
Balanced order (middle first)	2	3
Mixed order	3	4
Sorted order	6	7

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

Interactive · edit the input

sorted keys

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

No condition evaluated on this step

Execution trace (dry run table)Show 17 steps

Step	Line	State	What happens
1	L1	keys=7	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.
2	L4	mid=3 segment=[0, 6]	Segment [0, 6] has 7 keys: the middle one, 40, becomes the root of this subtree.
3	L4	mid=1 segment=[0, 2]	Segment [0, 2] has 3 keys: the middle one, 20, becomes the root of this subtree.
4	L4	mid=0 segment=[0, 0]	Segment [0, 0] has 1 key: the middle one, 10, becomes the root of this subtree.
5	L2	segment=[0, -1]	The segment [0, -1] is empty: that child is null.
6	L2	segment=[1, 0]	The segment [1, 0] is empty: that child is null.
7	L4	mid=2 segment=[2, 2]	Segment [2, 2] has 1 key: the middle one, 30, becomes the root of this subtree.
8	L2	segment=[2, 1]	The segment [2, 1] is empty: that child is null.
9	L2	segment=[3, 2]	The segment [3, 2] is empty: that child is null.
10	L4	mid=5 segment=[4, 6]	Segment [4, 6] has 3 keys: the middle one, 60, becomes the root of this subtree.
11	L4	mid=4 segment=[4, 4]	Segment [4, 4] has 1 key: the middle one, 50, becomes the root of this subtree.
12	L2	segment=[4, 3]	The segment [4, 3] is empty: that child is null.
13	L2	segment=[5, 4]	The segment [5, 4] is empty: that child is null.
14	L4	mid=6 segment=[6, 6]	Segment [6, 6] has 1 key: the middle one, 70, becomes the root of this subtree.
15	L2	segment=[6, 5]	The segment [6, 5] is empty: that child is null.
16	L2	segment=[7, 6]	The segment [7, 6] is empty: that child is null.
17	L7	height=2 minimum height=2	Height 2 for 7 keys: the smallest possible height is 2, so this tree is as short as a binary tree can be.

25.05.5

Random insertion trees

If the keys arrive in a uniformly random order, the tree is usually reasonably short: the **average depth** of a node is about 2 ln n, roughly 1.39 log2 n, and the height also grows logarithmically, with a constant factor above the optimum. A simulation of random insertion orders, averaged over 1,000 trials for n up to 1,000 and over 100 trials for n = 10,000, gave an average height of about 5.8 for n = 15, 12.3 for n = 100, 21.1 for n = 1,000 and 30.5 for n = 10,000, against a minimum possible height of 3, 6, 9 and 13.

So a random BST is a constant factor from perfect, which is why randomising the insertion order (shuffle the input first) is a cheap fix when the keys are all known in advance. When keys arrive online in an order you do not control, you need the balancing of the next chapter, or a treap, which uses random priorities to get the random-tree shape back.

n	15	100	1,000	10,000
Average height of a random BST	5.8	12.3	21.1	30.5
Minimum possible height ⌊log2 n⌋	3	6	9	13

Practice ladder

Now try it yourself

Easy

Convert Sorted Array to Binary Search Tree
Minimum Height Trees (concept)

Medium

Convert Sorted List to Binary Search Tree
Balance a Binary Search Tree

Advanced

Unique Binary Search Trees II
Number of Ways to Reorder Array to Get Same BST

Key takeaways

The middle of the sorted keys as root, recursively, gives a minimum-height BST in O(n).
Sorted insertion order builds a chain of height n - 1 and O(n) operations.
Shape follows insertion order: the same 7 keys give heights 2, 3 or 6.
A random insertion order gives a height that grows like log n, a constant factor above optimal (about 2.3 times the minimum at n = 1,000 in the simulation).