Trees
A tree is a hierarchical data structure of nodes connected by edges, with one root and no cycles — each node has children, forming branches. Trees model anything naturally nested or hierarchical: file systems, the DOM, org charts, decision processes, parsed expressions. They also power efficient ordered operations: a balanced search tree gives O(log n) insert, lookup, and delete while keeping data sorted — something a hash table can't do.
The most important family is the binary search tree (BST), where each node's left subtree holds smaller values and its right subtree larger ones. That ordering invariant is what enables fast search — as long as the tree stays balanced, which is the central concern.
TL;DR
- A tree is hierarchical: a root, nodes, and branches, no cycles.
- A binary search tree (BST) keeps values ordered for O(log n) search.
- Balance is everything — an unbalanced BST degrades to O(n).
- Traverse with in/pre/post-order (DFS) or level-order (BFS).
Quick Example
A binary tree node points to its children; ordering makes it a BST:
Core Concepts
- Root — the top node; leaf — a node with no children; height — longest root-to-leaf path.
- Binary tree — each node has at most two children.
- Binary search tree (BST) — a binary tree with the ordering invariant (left < node < right), enabling O(log n) search by halving the search space at each step.
Why Balance Matters
A BST's O(log n) performance depends on it being balanced (height ~log n). Insert sorted data into a naive BST and it degenerates into a glorified linked list — height n, operations O(n):
Self-balancing trees (AVL, red-black) automatically rotate to stay balanced, guaranteeing O(log n). Most language standard libraries' ordered maps/sets use a balanced tree (often red-black) under the hood.
Traversals
- In-order (left, node, right) — visits a BST in sorted order.
- Pre-order (node, left, right) — copy/serialize a tree.
- Post-order (left, right, node) — delete/evaluate (children before parent).
- Level-order (BFS) — breadth-first, level by level (uses a queue).
The first three are depth-first and naturally recursive.
Specialized Trees
- Heap — a tree keeping the min or max at the root; O(1) peek, O(log n) insert/extract. Powers priority queues (see Core Data Structures).
- B-tree / B+-tree — wide, balanced trees optimized for disk; the basis of database and filesystem indexes (see Database Indexing).
- Trie — a tree keyed by string prefixes; great for autocomplete and dictionaries.
Best Practices
- Use a self-balancing tree (or your language's ordered map/set) when you need ordered O(log n) operations — don't hand-roll a plain BST for production.
- Choose a tree over a hash when you need ordering: range queries, sorted iteration, nearest-key.
- Use in-order traversal to read a BST in sorted order.
- Watch recursion depth on deep/unbalanced trees — use iterative traversal if needed.
- Reach for a trie for prefix-based lookups (autocomplete).
Common Mistakes
A plain BST with sorted inserts
Using a tree when a hash table is enough
FAQ
When should I use a tree instead of a hash table?
Use a tree (specifically a balanced BST / ordered map) when you need ordering: range queries ("all keys between X and Y"), sorted iteration, or finding the nearest key. A hash table gives faster O(1) lookups but has no order. So if you only do exact key lookups, use a hash table; if you also need sorted traversal or ranges, use a balanced tree. Many languages' TreeMap/std::map are exactly this ordered-tree structure.
Why does a binary search tree need to be balanced?
The BST's O(log n) performance comes from halving the search space at each level, which requires the height to be ~log n. If the tree becomes lopsided — for example, inserting already-sorted data into a naive BST — it degenerates into a chain of height n, and operations become O(n), no better than a list. Self-balancing trees (AVL, red-black) perform rotations on insert/delete to keep the height logarithmic, guaranteeing O(log n).
What's the difference between the tree traversals?
They differ in when you visit a node relative to its children. In-order (left, node, right) visits a BST in sorted order. Pre-order (node, then children) is used to copy or serialize a tree. Post-order (children, then node) processes children first — useful for deleting or evaluating. Level-order (BFS) visits breadth-first, level by level, using a queue. The first three are depth-first and recursive; level-order is iterative with a queue.
What are B-trees and why do databases use them?
A B-tree is a balanced tree where each node holds many keys and has many children, keeping it short and wide. That shape minimizes disk reads — each node maps to a disk page, so even huge datasets need only a few levels (a few disk seeks) to reach any key. Databases and filesystems use B-trees (and B+-trees) for indexes because they provide O(log n) lookups and efficient range scans while playing well with block-based storage. See Database Indexing.
Related Topics
- Core Data Structures — Where trees and heaps fit
- Recursion — Tree traversal is recursive
- Graph Algorithms — Trees are acyclic graphs
- Hash Tables — The unordered alternative
- Database Indexing — B-trees in practice