Tree data structures compared
BST, balanced BST, trie, segment tree and Fenwick tree: the operations each supports, whether it handles updates, and which problem calls for which tree.
| Algorithm | Time | Space | Keyed by | Core operations | Updates | Difficulty |
|---|---|---|---|---|---|---|
| BSTBinary search trees | O(h) | O(h) | Comparable values | Search, insert, delete, predecessor / successor | ✓ | Intermediate |
| Balanced BSTHow balancing works | O(log n) | O(n) | Comparable values | Everything a BST does at guaranteed O(log n); range queries, k-th smallest | ✓ | Hard |
| TrieTries | O(L) | O(ΣL) | Characters of a string | Insert, lookup, prefix lookup | ✓ | Intermediate |
| Segment TreeSegment trees | O(log n) | O(n) | Array index | Range query (sum, max, min, anything mergeable), point or range update | ✓ | Hard |
| Fenwick Tree (BIT)Fenwick trees | O(log n) | O(n) | Array index | Prefix sum, point update | ✓ | Hard |
When to pick which
Teaching and interviews: how 'ordered and dynamic' reaches O(h). In practice nobody hand-writes an unbalanced BST.
You need an ordered set that keeps changing: C++ `map` / `set`, Java `TreeMap`. When a hash table cannot answer 'smallest value above k', this can.
When prefixes are the point: autocomplete, counting by prefix, longest common prefix, a bitwise trie for maximum XOR.
Range queries plus updates where the query is more than a sum (max, GCD, range assignment with lazy propagation). The most capable and the most code.
Range sum plus point update and nothing else: ten lines, smaller constants than a segment tree. First choice for inversion counting and dynamic ranking.
Choosing guide
- Ordered and changing → a balanced tree (use the built-in one). Only membership → a hash table is faster. Static data → a sorted array with binary search is enough.
- Range sums, static → prefix sums (O(1) query). Range sums, with updates → Fenwick. Range max / min with updates → segment tree.
- Range updates (add to or assign a whole range) → segment tree with lazy propagation. Fenwick only manages the 'range add, point query' variant.
- String keys and prefix questions → a trie. String keys but only equality → a hash table; a trie has no edge.
- k-th smallest, ranks → a balanced tree with subtree sizes, or a Fenwick tree over the value domain, which is easier to write once values are compressed.