Computer Science
A hierarchical data structure consisting of nodes connected by edges, with one root node and zero or more subtrees.
The topmost node. Every tree has exactly one root. It has no parent.
A node with no children. These are the terminal nodes at the bottom of the tree.
Depth = distance from root. Height = longest path from node to any leaf.
Each node (except root) has one parent. A node can have zero or more children.
A tree consisting of a node and all its descendants. Every node forms a subtree.
The link between a parent and child. A tree with N nodes has exactly N-1 edges.
Trees model parent-child relationships naturally — file systems, DOM, organization charts, and more.
Binary Search Trees (BST) support O(log n) lookup, insertion, and deletion when balanced.
Visit every node systematically via DFS (pre/in/post-order) or BFS (level-order) in O(n).
Tries (prefix trees) power autocomplete, spell checkers, and IP routing tables.
Balanced trees (AVL, Red-Black) keep data sorted while supporting dynamic insertions and deletions.
Each node has at most 2 children (left and right).
Max nodes at level d = 2^d
Left < Parent < Right. Enables O(log n) search.
search(key) → compare & branch
Self-balancing BSTs that guarantee O(log n) operations.
Balance factor ∈ {-1, 0, 1}
Complete binary tree where parent ≥ children (max-heap).
peek() → O(1), insert → O(log n)
Each node represents a character. Paths form words.
search(prefix) → O(m), m = len
Multi-child balanced trees used in databases and file systems.
Used by PostgreSQL, SQLite, NTFS
| Operation | Average | Worst (unbalanced) |
|---|---|---|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
| Traversal | O(n) | O(n) |
Directories and files form a tree hierarchy.
The browser's Document Object Model is a tree of elements.
B-Trees power SQL indexes for fast row lookups.
ML models that classify data through branching decisions.
Commits form a directed acyclic graph — a tree-like structure.
IP tries route packets efficiently through prefix matching.