Core Concept Mastery • DSA Module
Trees are non-linear, hierarchical data structures. Binary trees allow at most 2 children per node. BSTs add ordering (Left < Root < Right) enabling O(log n) search. Traversal is O(n), operations depend on height. Balanced trees give O(log n), skewed trees give O(n).
Quick recall: 'Tree = hierarchical, BST = ordered, Balanced = O(log n), Skewed = O(n), Traversal = O(n), Inorder(BST) = sorted.' These one-liners help you answer questions without recalculating everything.
PREorder = Process Root Early (before children)
INorder = Process Root In the middle (between children)
POSTorder = Process Root Last (after children)
The Golden Rules of Trees
Core Concepts
1. Tree = Non-linear, Hierarchical — branches in multiple directions, parent-child relationships
2. Binary Tree = At most 2 children — not exactly 2, can have 0, 1, or 2
3. BST = Binary Tree + Ordering — Left < Root < Right property
4. Height matters — Balanced = O(log n), Skewed = O(n)
Key Formulas
Traversal Orders
Complexity Cheat Sheet
Special Properties
Common Mistakes to Avoid
Exam Strategy
1. Identify tree type first (binary tree vs BST)
2. Check if balanced (affects complexity)
3. Remember traversal is always O(n)
4. Use formulas for node/height calculations
5. Watch for skewed tree traps
This cheat sheet consolidates key facts for quick exam review. Memorizing these shortcuts helps you answer questions quickly and avoid common mistakes. These are the essential facts that appear repeatedly in exams.
"What are the key facts to remember about trees for exams?"
Key facts: Trees are non-linear and hierarchical. Binary trees have at most 2 children. BSTs add ordering property (Left < Root < Right) enabling O(log n) search when balanced. Traversal is always O(n). Inorder traversal of BST gives sorted order. Balanced trees give O(log n) operations, skewed trees give O(n).