JAVA-201 · Lesson 10 of 12 · 25 min
Binary search trees
▶ Video coming soon A video version of this lesson is on the way.
Lesson 6 promised that TreeMap's O(log n) came from a balanced tree, and lesson 9 showed how much a data structure teaches when you build it yourself. The plan for Friday, April 2, 2027, the week after Good Friday, combines the two. Hamza builds a binary search tree of part codes, the structure underneath TreeMap and TreeSet, and finds out what balancing protects against by feeding his tree the one kind of input that breaks it.
Trees and their vocabulary
A tree is a linked structure in which each node can have several children but only one parent. The node with no parent is the root. Nodes with no children are leaves. In a binary tree, each node has at most two children, called left and right. The depth of a node is how many links separate it from the root, and the height of the tree is the depth of its deepest leaf. A tree of height h has at most 2^(h+1) − 1 nodes, so a well-shaped tree of 600 parts needs a height of only about 9.
The search-tree rule
A binary search tree, or BST, adds one rule: for every node, all keys in its left subtree are smaller than its key and all keys in its right subtree are larger. Searching then works like a guessing game. Start at the root; if the key you want is smaller, go left, if larger, go right, and stop when you find it or run out of tree. Each step discards a whole subtree, so a search takes at most height + 1 comparisons.
public class Main {
public static void main(String[] args) {
CodeTree t = new CodeTree();
for (String c : new String[] {"MOUNT", "BELL", "SADDLE", "AXLE", "CABLE", "PAD", "TUBE"}) t.add(c);
for (String c : new String[] {"PAD", "TUBE", "AXLE", "GRIPS"}) {
System.out.println(c + ": " + (t.contains(c) ? "found" : "not found") + " after " + t.comparisons + " comparisons");
}
}
}
class CodeTree {
private static class Node {
final String key;
Node left, right;
Node(String key) { this.key = key; }
}
private Node root;
int comparisons;
void add(String key) {
root = add(root, key);
}
private Node add(Node n, String key) {
if (n == null) return new Node(key);
int c = key.compareTo(n.key);
if (c < 0) n.left = add(n.left, key);
else if (c > 0) n.right = add(n.right, key);
return n;
}
boolean contains(String key) {
comparisons = 0;
Node n = root;
while (n != null) {
comparisons++;
int c = key.compareTo(n.key);
if (c == 0) return true;
n = c < 0 ? n.left : n.right;
}
return false;
}
}PAD: found after 3 comparisons TUBE: found after 3 comparisons AXLE: found after 3 comparisons GRIPS: not found after 3 comparisons
What this code does
Seven codes are added in an order that gives a well-shaped tree with MOUNT at the root. contains goes left or right at each node, so PAD and TUBE are found in three comparisons and AXLE in three as well. GRIPS is not in the tree, and the search gives up after three comparisons when it reaches an empty spot.
Inserting with recursion
Insertion follows the same path as a search. When the search falls off the tree, at a null child, that is exactly where the new key belongs. The add method above is recursive: add(n, key) returns the root of the subtree after the insertion, and each caller stores the result back into its left or right link. When n is null, the method returns a brand-new node, and that return value is what links it into its parent. A key that is already present is ignored, which makes the tree behave like a set.
Recursion fits trees naturally, because every subtree is itself a tree. The pattern "handle the empty case, otherwise do something with this node and recurse into one or both children" solves most tree problems in a few lines. The iterative loop in contains works too and avoids using the call stack, which matters for very deep trees.
Traversals: visiting every node
There are three classic ways to visit every node of a binary tree, named for when the node itself is visited relative to its children. In-order visits the left subtree, then the node, then the right subtree. Pre-order visits the node first; post-order visits it last. In a BST, in-order traversal visits the keys in sorted order, which is how a TreeMap iterates. Pre-order is useful for copying a tree, and post-order for deleting one, since children are handled before their parent.
import java.util.*;
public class Main {
public static void main(String[] args) {
CodeTree t = new CodeTree();
for (String c : new String[] {"MOUNT", "BELL", "SADDLE", "AXLE", "CABLE", "PAD", "TUBE"}) t.add(c);
System.out.println("in-order: " + t.inOrder());
System.out.println("pre-order: " + t.preOrder());
System.out.println("smallest " + t.min() + ", largest " + t.max() + ", height " + t.height());
}
}
class CodeTree {
private static class Node {
final String key;
Node left, right;
Node(String key) { this.key = key; }
}
private Node root;
void add(String key) { root = add(root, key); }
private Node add(Node n, String key) {
if (n == null) return new Node(key);
int c = key.compareTo(n.key);
if (c < 0) n.left = add(n.left, key);
else if (c > 0) n.right = add(n.right, key);
return n;
}
List<String> inOrder() { List<String> out = new ArrayList<>(); inOrder(root, out); return out; }
private void inOrder(Node n, List<String> out) {
if (n == null) return;
inOrder(n.left, out);
out.add(n.key);
inOrder(n.right, out);
}
List<String> preOrder() { List<String> out = new ArrayList<>(); preOrder(root, out); return out; }
private void preOrder(Node n, List<String> out) {
if (n == null) return;
out.add(n.key);
preOrder(n.left, out);
preOrder(n.right, out);
}
String min() { Node n = root; while (n.left != null) n = n.left; return n.key; }
String max() { Node n = root; while (n.right != null) n = n.right; return n.key; }
int height() { return height(root); }
private int height(Node n) {
if (n == null) return -1;
return 1 + Math.max(height(n.left), height(n.right));
}
}in-order: [AXLE, BELL, CABLE, MOUNT, PAD, SADDLE, TUBE] pre-order: [MOUNT, BELL, AXLE, CABLE, SADDLE, PAD, TUBE] smallest AXLE, largest TUBE, height 2
What this code does
In-order traversal visits left, node, right, so it returns the seven codes in alphabetical order. Pre-order starts with the root, MOUNT, and is the order in which you could re-insert the keys to rebuild the same tree. The smallest key is found by always going left and the largest by always going right, and the height of this tree is 2.
| Traversal | Order | For this tree | Typical use |
|---|---|---|---|
| In-order | left, node, right | AXLE, BELL, CABLE, MOUNT, PAD, SADDLE, TUBE | sorted output |
| Pre-order | node, left, right | MOUNT, BELL, AXLE, CABLE, SADDLE, PAD, TUBE | copying or saving a tree |
| Post-order | left, right, node | AXLE, CABLE, BELL, PAD, TUBE, SADDLE, MOUNT | deleting or sizing subtrees |
| Level order | by depth, using a queue | MOUNT, BELL, SADDLE, AXLE, CABLE, PAD, TUBE | printing level by level |
The fourth row, level-order traversal, visits the root, then all nodes at depth 1, then depth 2 and so on. It uses a queue from lesson 4: put the root in, and repeatedly take a node out and put its children in. It is the tree version of breadth-first search, which JAVA-205 uses for graphs.
When the shape goes wrong
A BST's speed depends entirely on its height. Insert the codes in a mixed order and the tree is bushy, with height near log₂ n. Insert them already sorted, as Kofi's spreadsheet export is, and every new key is larger than all the others, so it always goes to the right. The tree becomes a chain, a degenerate tree, with height n − 1, and searching it is no better than searching a linked list.
import java.util.*;
public class Main {
public static void main(String[] args) {
List<Integer> codes = new ArrayList<>();
for (int i = 1; i <= 612; i++) codes.add(i);
IntTree sorted = new IntTree();
for (int c : codes) sorted.add(c);
Collections.shuffle(codes, new Random(7));
IntTree shuffled = new IntTree();
for (int c : codes) shuffled.add(c);
System.out.println("612 keys inserted in sorted order: height " + sorted.height()
+ ", worst search " + (sorted.height() + 1) + " comparisons");
System.out.println("612 keys inserted in shuffled order: height " + shuffled.height()
+ ", worst search " + (shuffled.height() + 1) + " comparisons");
System.out.println("a perfectly balanced tree would have height " + (int) Math.floor(Math.log(612) / Math.log(2)));
}
}
class IntTree {
private static class Node { final int key; Node left, right; Node(int k) { key = k; } }
private Node root;
void add(int key) {
if (root == null) { root = new Node(key); return; }
Node n = root;
while (true) {
if (key < n.key) { if (n.left == null) { n.left = new Node(key); return; } n = n.left; }
else if (key > n.key) { if (n.right == null) { n.right = new Node(key); return; } n = n.right; }
else return;
}
}
int height() { return height(root); }
private int height(Node n) {
if (n == null) return -1;
int h = -1;
java.util.ArrayDeque<Node> level = new java.util.ArrayDeque<>();
level.add(n);
while (!level.isEmpty()) {
h++;
for (int i = level.size(); i > 0; i--) {
Node x = level.poll();
if (x.left != null) level.add(x.left);
if (x.right != null) level.add(x.right);
}
}
return h;
}
}612 keys inserted in sorted order: height 611, worst search 612 comparisons 612 keys inserted in shuffled order: height 20, worst search 21 comparisons a perfectly balanced tree would have height 9
What this code does
Inserting the codes in sorted order sends every key to the right, so the tree is a chain of height 611 and a search can take 612 comparisons. The same keys in a shuffled order, with a fixed seed so the result is repeatable, give a tree only about twice as tall as the ideal of 9. The insert and height methods are written with loops and a queue so the deep chain does not overflow the call stack.
That height of 611 is why the recursive version of add, which makes one method call per level, can fail on a degenerate tree with StackOverflowError: each level of recursion uses a frame on the call stack, and a few thousand levels can exhaust it. Balanced trees never get deep enough for this to matter.
Balanced trees
Self-balancing trees fix the shape automatically. After each insertion or deletion they check a balance condition and, when it is broken, perform small local restructurings called rotations that lift one subtree and lower another while keeping the search-tree rule. An AVL tree keeps the heights of every node's two subtrees within one of each other. A red-black tree, the kind TreeMap uses, keeps a looser rule based on node colors, which needs fewer rotations and still guarantees a height of at most about 2 log₂ n. Either way, every operation is O(log n) in the worst case.
You will rarely write a balancing tree yourself; TreeMap and TreeSet are excellent. The value of this lesson is knowing what they guarantee and why, and recognizing the warning signs in your own structures: anything that can become a chain when given sorted input needs balancing, shuffling or a different design.
Deleting a key
Deletion is the hardest BST operation because removing a node must leave the rule intact. There are three cases. A leaf is simply removed. A node with one child is replaced by that child. A node with two children is replaced by its in-order successor, the smallest key in its right subtree, which is then deleted from that subtree; the successor has at most one child, so that second deletion is one of the easy cases.
import java.util.*;
public class Main {
public static void main(String[] args) {
CodeTree t = new CodeTree();
for (String c : new String[] {"MOUNT", "BELL", "SADDLE", "AXLE", "CABLE", "PAD", "TUBE", "WHEEL"}) t.add(c);
System.out.println("start: " + t.inOrder() + " root " + t.rootKey());
t.remove("AXLE");
System.out.println("remove a leaf: " + t.inOrder());
t.remove("TUBE");
System.out.println("remove one child: " + t.inOrder());
t.remove("MOUNT");
System.out.println("remove the root: " + t.inOrder() + " root " + t.rootKey());
}
}
class CodeTree {
private static class Node { String key; Node left, right; Node(String k) { key = k; } }
private Node root;
void add(String key) { root = add(root, key); }
private Node add(Node n, String key) {
if (n == null) return new Node(key);
int c = key.compareTo(n.key);
if (c < 0) n.left = add(n.left, key); else if (c > 0) n.right = add(n.right, key);
return n;
}
void remove(String key) { root = remove(root, key); }
private Node remove(Node n, String key) {
if (n == null) return null;
int c = key.compareTo(n.key);
if (c < 0) { n.left = remove(n.left, key); return n; }
if (c > 0) { n.right = remove(n.right, key); return n; }
if (n.left == null) return n.right;
if (n.right == null) return n.left;
Node s = n.right;
while (s.left != null) s = s.left;
n.key = s.key;
n.right = remove(n.right, s.key);
return n;
}
String rootKey() { return root.key; }
List<String> inOrder() { List<String> out = new ArrayList<>(); walk(root, out); return out; }
private void walk(Node n, List<String> out) { if (n == null) return; walk(n.left, out); out.add(n.key); walk(n.right, out); }
}start: [AXLE, BELL, CABLE, MOUNT, PAD, SADDLE, TUBE, WHEEL] root MOUNT remove a leaf: [BELL, CABLE, MOUNT, PAD, SADDLE, TUBE, WHEEL] remove one child: [BELL, CABLE, MOUNT, PAD, SADDLE, WHEEL] remove the root: [BELL, CABLE, PAD, SADDLE, WHEEL] root PAD
What this code does
AXLE is a leaf, so its parent's link is simply set to null, and TUBE has one child, WHEEL, which takes its place. MOUNT, the root, has two children, so its key is replaced by its in-order successor PAD, the smallest key on its right, and PAD is then removed from the right subtree. After every removal the in-order traversal is still sorted, which shows the search-tree rule survived.
| Operation | Balanced BST (TreeMap) | Plain BST, random input | Plain BST, sorted input |
|---|---|---|---|
| contains, add, remove | O(log n) guaranteed | O(log n) on average | O(n) |
| min, max | O(log n) | O(log n) on average | O(n) |
| In-order traversal | O(n) | O(n) | O(n) |
| Height for 612 keys | at most about 18 | typically about 20 | 611 |
Try it yourself
Counting the nodes
Complete the recursive size(Node n) method so it returns the number of nodes in the subtree: zero for an empty tree, otherwise one plus the sizes of the left and right subtrees.
The program should print 7 codes in the tree.
public class Main {
public static void main(String[] args) {
CodeTree t = new CodeTree();
for (String c : new String[] {"MOUNT", "BELL", "SADDLE", "AXLE", "CABLE", "PAD", "TUBE", "BELL"}) t.add(c);
System.out.println(t.size() + " codes in the tree");
}
}
class CodeTree {
private static class Node { final String key; Node left, right; Node(String k) { key = k; } }
private Node root;
void add(String key) { root = add(root, key); }
private Node add(Node n, String key) {
if (n == null) return new Node(key);
int c = key.compareTo(n.key);
if (c < 0) n.left = add(n.left, key); else if (c > 0) n.right = add(n.right, key);
return n;
}
int size() { return size(root); }
private int size(Node n) {
return 0;
}
}Try it yourself
Codes in a range
Complete between(Node n, String lo, String hi, List<String> out) so it adds, in sorted order, every key from lo to hi inclusive. Walk the tree in order, but skip a left subtree when the node's key is not greater than lo, and a right subtree when it is not less than hi.
The program should print [BELL, CABLE, MOUNT, PAD].
import java.util.*;
public class Main {
public static void main(String[] args) {
CodeTree t = new CodeTree();
for (String c : new String[] {"MOUNT", "BELL", "SADDLE", "AXLE", "CABLE", "PAD", "TUBE"}) t.add(c);
System.out.println(t.between("B", "PB"));
}
}
class CodeTree {
private static class Node { final String key; Node left, right; Node(String k) { key = k; } }
private Node root;
void add(String key) { root = add(root, key); }
private Node add(Node n, String key) {
if (n == null) return new Node(key);
int c = key.compareTo(n.key);
if (c < 0) n.left = add(n.left, key); else if (c > 0) n.right = add(n.right, key);
return n;
}
List<String> between(String lo, String hi) {
List<String> out = new ArrayList<>();
between(root, lo, hi, out);
return out;
}
private void between(Node n, String lo, String hi, List<String> out) {
if (n == null) return;
out.add(n.key);
}
}Common mistakes
MistakeInserting sorted data into a plain BST.
InsteadUse TreeMap or TreeSet, which balance themselves, or shuffle the input first.
MistakeForgetting to store the result of the recursive add back into the child link.
InsteadWrite n.left = add(n.left, key); the new node is linked in through that return value.
MistakeWriting recursion for a tree that may be very deep.
InsteadUse loops with an explicit stack or queue, or make sure the tree is balanced.
MistakeDeleting a node with two children by simply removing it.
InsteadReplace its key with the in-order successor and delete the successor from the right subtree.
MistakeExpecting pre-order traversal to give sorted keys.
InsteadOnly in-order traversal of a BST visits keys in sorted order.
Summary and key terms
- A tree is a linked structure with a root, children and leaves, and a binary tree gives each node at most two children; height is the depth of the deepest leaf.
- A binary search tree keeps smaller keys in each node's left subtree and larger ones in its right, so a search goes left or right at each node and takes at most height plus one comparisons.
- Insertion follows the search path and adds a node where it falls off the tree, often written recursively.
- In-order traversal visits keys in sorted order; pre-order, post-order and level-order have other uses.
- A BST's speed depends on its shape: sorted input makes a degenerate chain of height n minus one with O(n) operations, while balanced shapes give O(log n).
- Self-balancing trees such as AVL and red-black trees use rotations to keep the height O(log n), and TreeMap uses a red-black tree.
- Deletion handles three cases: a leaf, one child, and two children, where the in-order successor takes the node's place.
- Tree
- A linked structure in which each node has one parent, except the root, and any number of children.
- Root
- The node at the top of a tree, with no parent.
- Leaf
- A node with no children.
- Binary tree
- A tree in which each node has at most two children, left and right.
- Height
- The number of links from the root to the deepest leaf.
- Binary search tree
- A binary tree with smaller keys on the left of each node and larger keys on the right.
- In-order traversal
- Visiting left subtree, node, then right subtree, which gives sorted order in a BST.
- Degenerate tree
- A tree shaped like a chain, with height n minus one.
- Rotation
- A local restructuring of a tree that changes its shape but keeps its order.
- AVL tree
- A self-balancing BST whose subtree heights differ by at most one at every node.
- In-order successor
- The next larger key, the smallest key in a node's right subtree.
- StackOverflowError
- The error thrown when recursion goes too deep for the call stack.
Practice problems
Work each problem on paper first, then reveal the answer to check.
Where is the smallest key in a BST?
Show answer
At the leftmost node: keep going left from the root.
Which traversal of a BST gives the keys in sorted order?
Show answer
In-order: left, node, right.
What happens to a plain BST when keys arrive in sorted order?
Show answer
It becomes a chain, so its operations become O(n).
How does a self-balancing tree keep its height low?
Show answer
It performs rotations after changes that break its balance rule.
What replaces a deleted node that has two children?
Show answer
Its in-order successor, the smallest key in its right subtree.
Lesson quiz · 5 questions
Score 60% or more to complete this lesson.
Create a free account to save your progress, take quizzes and earn a certificate.