BST / Ordered Set

Binary search trees and the ordered sets built on them: search, insert and delete along one path, floor and ceiling queries, and the calendar-style problems they solve.

Overview

A binary search tree (BST) is a binary tree with one rule: every key in a node's left subtree is smaller than the node's key, and every key in its right subtree is larger. The rule covers whole subtrees, not just the two children. Because of it, search, insert and delete all follow a single path from the root, and an inorder traversal lists the keys in sorted order.

An ordered set or ordered map (Java's TreeSet and TreeMap, C++'s std::set and std::map) is a self-balancing BST behind a library interface: Java documents a red-black tree, and C++ requires logarithmic search, insert and removal, which its standard libraries usually meet with a red-black tree. You reach for one whenever you need a collection that stays sorted while items come and go: the nearest value above or below a key, all keys in a range, or the next free slot in a calendar.

The rule and the sample tree

Inorder traversal — 2, 4, 6, 8, 10, 12, 14 (sorted)
Smallest key — 2, the leftmost node
Largest key — 14, the rightmost node
Height — 2 edges, about log2(7)

Search follows one path

The search starts at the root. If the key you want is smaller, go left; if larger, go right; if equal, stop. Each step drops one level, so the cost is O(h), where h is the height.

1 — 8 — 6 is smaller — left
2 — 4 — 6 is larger — right
3 — 6 — equal — found

Searching for 5 follows the same path and then steps left from 6 into None: not in the tree. The node where the search fell off (6) is exactly where insert would attach 5.

Insert: search, then attach at the empty spot

An insert runs the same search as a lookup. When it reaches None, it creates the new node there. Nothing else in the tree moves, so insert is also O(h). Inserting 5 into the sample tree attaches it as the left child of 6.

1 — 8 — smaller — left
2 — 4 — larger — right
3 — 6 — smaller — left, which is None: attach 5 here

Delete: three cases

Deleting a node depends on how many children it has.

The smallest key of the right subtree is the node's inorder successor: the next key in sorted order. Copying it up keeps the BST rule, because it is larger than everything on the left and smaller than everything else on the right. The inorder predecessor (the largest key of the left subtree) works the same way.

2 — leaf — 4's left pointer becomes None — 4, 6, 8, 10, 12, 14
4 (after 2 is gone) — one child — 8's left pointer now points at 6 — 6, 8, 10, 12, 14
8 from the original tree — two children — 10 is the smallest key on the right; 8 becomes 10, and the old 10 node is unlinked — 2, 4, 6, 10, 12, 14

Balance is everything

The costs above are O(h). On a balanced tree h is about log2(n). On a chain h is n minus 1, and every operation is O(n). A plain BST becomes a chain when keys arrive in sorted order.

Balanced — 2 — about 20 — O(log n)
Chain — 6 — 999,999 — O(n)

Self-balancing trees fix this by rotating nodes after inserts and deletes so that h stays O(log n). AVL trees keep the two child heights within one of each other; red-black trees allow a looser balance and do fewer rotations. Java's TreeMap is a red-black tree and guarantees log(n) time for containsKey, get, put and remove. You rarely write a balancing tree yourself; you say which library type gives you one.

Floor, ceiling and neighbors

Sorted order makes four questions cheap, all in O(h) by walking one root-to-leaf path and remembering the best candidate seen.

Floor — largest key less than or equal to 7 — 6 — floorKey, floor
Ceiling — smallest key greater than or equal to 7 — 8 — ceilingKey, ceiling
Lower — largest key strictly less than 7 — 6 — lowerKey, lower
Higher — smallest key strictly greater than 7 — 8 — higherKey, higher

A range query, all keys between 5 and 11, is an inorder walk that skips left subtrees below 5 and right subtrees above 11: it costs O(h + m) for m results. Java offers it as subMap(5, true, 11, true); the two-argument subMap(5, 11) excludes the upper bound.

Ordered sets in each language

Java — TreeSet, TreeMap — red-black tree — guaranteed O(log n)
C++ — std::set, std::map — usually a red-black tree — O(log n) required by the standard
Python, standard library — none; bisect on a sorted list — plain list — O(log n) search but O(n) insert, because the list shifts elements
Python, third party — sortedcontainers.SortedList — a list of sorted sublists, not a tree — about O(log n) for add, remove, index and bisect
JavaScript — none built in — write a small class, or use a sorted array with binary search

In Python, say which one you assume. For a few thousand items the bisect list is fine and simple; if you need O(log n) inserts, name SortedList or describe a balanced tree.

A calendar with an ordered map

My Calendar I asks you to accept a booking [start, end) only if it overlaps no earlier booking. With bookings kept in an ordered map from start to end, one lookup on each side decides it: the booking that starts just before the new start must end by the new start, and the booking that starts at or after the new start must start at or after the new end.

[10, 20) — none — none — nothing to hit — accepted
[15, 25) — [10, 20) — none — 20 is not <= 15 — rejected
[20, 30) — [10, 20) — none — 20 <= 20 — accepted
[5, 10) — none — [10, 20) — 10 <= 10 — accepted

Each booking costs O(log n) with a tree map. With a Python bisect list the two lookups are still O(log n) but the insert is O(n), which is fine for the problem's limits.

What you will be able to do

State the BST rule as a rule about whole subtrees and use it to search, insert and delete along one path.
Explain the three delete cases and why the inorder successor keeps the tree valid.
Say why a plain BST can degrade to O(n), and name the library type that guarantees O(log n).
Use floor, ceiling and range queries to solve calendar, nearest-value and interval problems.
Pick the right ordered structure in Python, Java or JavaScript and state its real costs.

When to use it

A collection that must stay sorted while items are added and removed
The nearest key above or below a value: floor, ceiling, predecessor, successor
Range queries: every key between low and high
Calendar and booking problems: does a new interval overlap an existing one
Streams where you need both fast inserts and sorted access
Order statistics such as the k-th smallest key, especially with subtree sizes stored in nodes

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio