BrewlearnTrees & BSTs in Java
Traversals (in/pre/post/level order), balanced trees, TreeMap as a red-black tree.
The BST rule
In a binary search tree, every node's left subtree holds smaller keys and its right subtree larger ones. Searching is a game of higher-or-lower: each step goes left or right, so search, insert and delete cost O(height).
N find(N n, int key) {
while (n != null && n.v() != key)
n = key < n.v() ? n.l() : n.r();
return n;
}Four ways to walk a tree
Take root 8 with children 3 and 10, where 3 has children 1 and 6. In-order (left, node, right) gives 1 3 6 8 10: sorted, for any BST. Pre-order prints the node before its subtrees, post-order after them. Level-order goes row by row using a queue: 8 3 10 1 6.
void inOrder(N n) {
if (n == null) return;
inOrder(n.l());
System.out.print(n.v() + " ");
inOrder(n.r());
}Node first
Same tree. What does pre-order print?
// 8
// / \
// 3 10
// / \
// 1 6
void pre(N n) {
if (n == null) return;
System.out.print(n.v() + " ");
pre(n.l()); pre(n.r());
}8 3 1 6 101 3 6 8 108 3 10 1 61 6 3 10 8
Show the answer
Pre-order prints the node, then its whole left subtree, then the right: 8, then 3 1 6, then 10. Post-order would finish both subtrees first and print the root last: 1 6 3 10 8.
Sorted input makes a stick
Insert 1, 2, 3, ..., n in order into a plain BST. Each key is larger than everything so far, so it always goes right. The "tree" becomes a chain of height n, and every operation becomes O(n), not O(log n).
// insert 1, 2, 3, 4:
// 1
// \
// 2
// \
// 3
// \
// 4TreeMap: a red-black tree
Self-balancing trees rotate nodes to keep height O(log n) whatever the insert order. Java's TreeMap and TreeSet are red-black trees: get, put and remove are O(log n) and keys stay sorted. Navigation methods: firstKey, floorKey(x) (largest <= x), ceilingKey(x) (smallest >= x), headMap(k) (keys < k, exclusive).
Navigating a TreeMap
What does this print?
var m = new TreeMap<Integer, String>();
m.put(30, "c"); m.put(10, "a"); m.put(20, "b");
IO.println(m.firstKey() + " " + m.floorKey(25));
IO.println(m.ceilingKey(25));
IO.println(m.headMap(20));10 20 30 {10=a}10 30 20 {10=a, 20=b}30 20 30 {10=a}
Show the answer
Keys are kept sorted: 10, 20, 30, so firstKey is 10. The largest key <= 25 is 20; the smallest key >= 25 is 30. headMap(20) is exclusive, so it holds only 10.
Trees at work
Use TreeMap when you need sorted keys or range queries: leaderboards, time-series lookups, "next available slot". Don't confuse it with HashMap's tree bins (only for collisions) or ConcurrentSkipListMap, which is a skip list. Database indexes use B-trees, cousins of the BST.
Key takeaways
- In-order traversal of a BST visits keys in sorted order
- Pre-order: node first; post-order: node last; level-order: use a queue
- Sorted inserts into a plain BST create a tall 'stick'
- TreeMap is a red-black tree: O(log n) and sorted keys
💡 A BST is a game of 'higher or lower': each answer rules out a whole branch.
Rudolf Bayer invented the structure in 1972 as "symmetric binary B-trees". Leonidas Guibas and Robert Sedgewick gave it the red-black name in 1978.
Practice questions
What does post(root) print for this tree?
// 4
// / \
// 2 6
// / \
// 1 3
void post(N n) {
if (n == null) return;
post(n.l()); post(n.r());
System.out.print(n.v() + " ");
}- 4 2 1 3 6
- 1 3 2 6 4
- 1 2 3 4 6
- 1 3 6 2 4
Check your answer
1 3 2 6 4. Post-order finishes both subtrees before printing the node: the left subtree gives 1 3 2, the right gives 6, and the root 4 comes last.
What data structure backs java.util.TreeMap?
- A hash table with tree bins
- A sorted array searched with binary search
- A red-black tree
- A skip list
Check your answer
A red-black tree. TreeMap is a red-black tree. HashMap uses tree bins only for collisions, and the skip list is ConcurrentSkipListMap.