Trees
Curriculum
Master hierarchical data structures through structural invariants, traversal patterns, and recursive thinking.
What This Category Is Really About
Parent-child relationships forming acyclic graphs. Each node has exactly one parent (except root). Structure enables divide-and-conquer.
Systematic ways to visit every node: preorder, inorder, postorder, level-order. Each pattern reveals different structural properties.
Properties maintained across operations: BST ordering, heap property, balance constraints. Invariants enable efficient operations.
Problems naturally split into left and right subtrees. Solve for subtrees, combine results. Tree structure matches recursive thinking.
Mental Model & Invariants
Trees are recursive structures where every subtree is itself a tree.
"A tree problem solved for the root and its subtrees is solved for the entire tree. Structural invariants hold at every node."
Break this, and the tree loses its defining properties.
BST Invariant
Left subtree values < node < right subtree values. Enables O(log n) search in balanced trees.
Height Invariant
Balanced trees maintain |height(left) - height(right)| ≤ 1. Guarantees logarithmic depth.
Heap Property
Parent ≥ children (max-heap) or parent ≤ children (min-heap). Enables O(1) min/max access.
Think Recursively
Define solution for a single node assuming subtrees are solved. Combine subtree results at current node.
When to Think "Trees"
sensorsStrong Signals
Hierarchical relationships (parent-child)
Need to search/insert/delete in sorted order
Range queries or interval problems
Path from root to leaf matters
Level-by-level processing required
Ancestor-descendant relationships
ruleStructure Signals
Data has natural parent-child structure
Need O(log n) operations on sorted data
Prefix/suffix relationships matter
Recursive decomposition applies naturally
Core Patterns You Must Master
Tree Traversals
Preorder, inorder, postorder, level-order. Each reveals different properties.
Visit every node exactly once in defined order.
Binary Search Trees
Ordered trees enabling O(log n) search, insert, delete.
Left < node < right at every node.
Path Problems
Root-to-leaf paths, path sums, lowest common ancestor.
Track state from root to current node.
Level-Order Processing
Process tree level by level using BFS.
All nodes at depth d processed before depth d+1.
Tree Construction
Build trees from traversals or other representations.
Inorder + (preorder or postorder) uniquely defines tree.
Balanced Trees
AVL, Red-Black trees maintaining height balance.
Height difference ≤ 1 at every node.
How to Learn This Category
Master Traversals First
Implement all four traversals (preorder, inorder, postorder, level-order) both recursively and iteratively. Understand what each reveals.
Understand BST Invariant
Practice BST operations. Verify invariant holds after every operation. Understand why inorder traversal yields sorted sequence.
Draw Trees on Paper
Visualize tree structure. Draw before coding. Trace recursive calls. See how subtree solutions combine at each node.
Identify Recursive Structure
Every tree problem: what do I do at this node? What do subtrees return? How do I combine results?
Practice Path Problems
Root-to-leaf paths, path sums, LCA. Learn to track state from root to current node. Understand backtracking in trees.
Master Level-Order (BFS)
Use queue for level-by-level processing. Understand when BFS is better than DFS. Practice zigzag and right-side view variants.
Canonical Problem List
auto_awesome_motionFoundation
Binary Tree Inorder Traversal
Implement inorder traversal recursively and iteratively.
Maximum Depth of Binary Tree
Find height of tree. Classic recursive structure.
Same Tree
Check if two trees are identical. Recursive comparison.
Invert Binary Tree
Mirror a tree. Swap left and right subtrees recursively.
Binary Tree Level Order Traversal
BFS traversal. Process level by level.
auto_awesome_motionIntermediate
Validate Binary Search Tree
Verify BST invariant holds at every node.
Binary Tree Right Side View
Rightmost node at each level. BFS or DFS with level tracking.
Lowest Common Ancestor of BST
Find LCA using BST property. First split point.
Path Sum II
Find all root-to-leaf paths with target sum. Backtracking.
Construct Binary Tree from Traversals
Build tree from inorder and preorder. Understand uniqueness.
Kth Smallest Element in BST
Inorder traversal yields sorted order. Count to k.
auto_awesome_motionAdvanced
Binary Tree Maximum Path Sum
Path can start and end anywhere. Track max at each node.
Serialize and Deserialize Binary Tree
Convert tree to string and back. Handle null nodes.
Binary Tree Cameras
Minimum cameras to monitor all nodes. Greedy + tree DP.
Recover Binary Search Tree
Two nodes swapped. Find and fix using inorder.
Common Mistakes
Not Checking for Null Nodes
Null pointer exceptions. Recursion doesn't terminate properly.
Always check if node is null before accessing properties. Make null check the base case.
Confusing Node Value with Node Reference
Comparing node.val when you should compare nodes. Or vice versa.
Be explicit: comparing values or comparing references? Different semantics.
Wrong Traversal Order
Using preorder when inorder is needed. Each traversal reveals different properties.
Understand what each traversal does. Inorder for BST gives sorted order. Postorder for bottom-up.
Not Maintaining BST Invariant
Checking only immediate children instead of entire subtrees.
Pass valid range down recursively. Left subtree must be < node, not just left child.
Forgetting to Return Values
Recursive calls made but results not used or returned.
Every recursive call should either return a value or modify shared state. Don't lose information.
Interview Guidance
What they test
- →Recursive thinking
- →Traversal pattern selection
- →Invariant maintenance
- →Edge case handling (null, single node)
Strategy
Draw the tree first. Show small examples. Articulate recursive structure: "For this node, I need X from left subtree and Y from right subtree, then combine as Z."
The Verbal Template
"If node is null, return [value]. This handles empty trees and leaf children."
"Get result from left subtree and right subtree. Each returns [what they compute]."
"At current node, combine subtree results: [how you merge/compare/aggregate]."
"Return [what this subtree contributes] to parent. Maintains recursive contract."
When You've Mastered It
Implement all traversals without hesitation
Identify correct traversal for problem instantly
Draw tree structure before coding
Articulate recursive decomposition clearly
Handle null nodes automatically
Verify BST invariant correctly
What This Unlocks Next
Graphs
Trees are special graphs. Graph algorithms extend tree concepts: DFS, BFS, cycle detection.
Tries
Specialized trees for string operations. Prefix matching, autocomplete, dictionary problems.
Heaps
Complete binary trees with heap property. Priority queues, top-K problems, streaming data.
Dynamic Programming on Trees
Tree DP combines recursion with memoization. Subtree problems with overlapping subproblems.