Key terms
- Root — the single node with no parent
- Leaf — a node with no children
- Height — maximum depth from root to leaf
Types of trees
- Binary Tree — each node has ≤ 2 children
- BST (Binary Search Tree) — left child < node < right child. Search O(log n)
- B-Tree — multi-way, balanced. The foundation of MySQL/PostgreSQL indexes
- Trie — string tree for fast prefix search (autocomplete)
Traversals
Pre-order (root → left → right), In-order (left → root → right; yields a sorted BST), Post-order, BFS (level by level).