Trees
A Tree is a hierarchical, non-linear data structure containing nodes connected by edges. The top node is the root. A Binary Search Tree (BST) requires left sub-nodes to be smaller and right sub-nodes to be larger.
Why It Exists
Linear search is too slow for large datasets, and sorted arrays are slow to update. BSTs resolve this by dividing search options on each step, enabling logarithmic searches and insertions.
Intuition for Beginners
“Think of a corporate organization chart. The CEO is the root. Each manager splits responsibilities. To find an employee, you navigate down divisions without scanning unrelated teams.”
Visual Explanation
Binary Search Tree (BST):
[20]
/ \
[10] [30]
/ \
[5] [15]DFS Tree Traversal
Push root node 1 to recursion stack. Visit node 1.
Complexity Analysis
| Operation | Time (Balanced) | Time (Skewed) | Notes |
|---|---|---|---|
| Search | O(log N) | O(N) | Skewed tree acts like a linked list |
| Insert | O(log N) | O(N) | Traverses tree height to leaf |
| Delete | O(log N) | O(N) | Requires link restructuring |
| Space | O(H) | O(N) | Height recursion overhead |
Production & Real World Applications
- •DOM Trees: Web browser rendering engines structuring HTML nested nodes.
- •B-Trees: Database indexing engines executing storage query plans.
Algorithmic Patterns
Exploring depth paths recursively: Preorder (NLR), Inorder (LNR - yields sorted BST values), Postorder (LRN).
Scanning nodes layer-by-layer using a queue.
Defending the Design (Interview Q&A)
Common Traps & Mistakes
- ⚠️Forgetting to handle tree imbalances (which turns O(log N) operations into O(N)).
- ⚠️Using recursion without checking null root base cases.