Trees appear intimidating because they combine:

• Hierarchy
• Recursion
• Subtree relationships
• Path-based logic
• Parent-child dependencies

But almost every tree problem falls into a small set of reusable patterns.

The key mental model:

Tree problem = Choose traversal direction + Decide what each recursive call should return

Once you master this idea, tree problems become systematic instead of chaotic.

---

Pattern Table (Simplified – 4 Columns Only)

Pattern	Typical Question Types	Keywords / Detection Cues	Why Use / Notes
DFS (Pre/In/Post Order)	Traversal, Expression evaluation	depth, recursion, left/right	Recursive or stack-based traversal.
BFS / Level Order	Level traversal, Shortest path	level, breadth, queue	Queue-based layer-by-layer traversal.
Binary Search Tree (BST)	Search/Insert/Delete	sorted, property, left < root	Exploit BST ordering property.
Tree Height / Diameter	Max depth, Longest path	height, depth, longest path	DFS returning subtree height.
LCA (Lowest Common Ancestor)	Common ancestor, Distance	ancestor, path, subtree	DFS or binary lifting.
Tree DP	Max path sum, House robber	child, subtree, combine	Post-order DP combining child results.
Segment Tree / BIT (Bonus)	Range queries, Updates	range, update, query	Logarithmic range operations.
Trie	Prefix search	prefix, search	Tree-based string indexing.

---

How to Choose the Correct Tree Pattern

When the input structure is a tree, ask:

1. Is the question asking to visit every node?
2. Is it about levels or distance from root?
3. Is the tree a Binary Search Tree?
4. Is it about longest path or depth?
5. Is it asking about relationship between two nodes?
6. Does each node depend on child results?
7. Is it about range queries on an array-like structure?
8. Is it about prefix matching in strings?

Each of these maps directly to a pattern below.

---

Full Explanation of Each Pattern

---

1. DFS (Preorder / Inorder / Postorder) – Common

When to use:

• Need to traverse entire tree
• Evaluate expressions
• Build or serialize tree

Keywords:

depth, recursion, left, right, traverse

Core Idea:

DFS explores deep before wide.

Three orders:

• Preorder → Root → Left → Right
• Inorder → Left → Root → Right
• Postorder → Left → Right → Root

When each is used:

• Inorder → Sorted output in BST
• Preorder → Copy/construct tree
• Postorder → When parent depends on children (very common)

Mental Trigger:

“Traverse entire tree recursively” → DFS

---

2. BFS / Level Order – Common

When to use:

• Level-by-level processing
• Shortest path in unweighted tree

Keywords:

level, breadth, queue

Core Idea:

Use a queue to process nodes layer by layer.

Typical Problems:

• Level order traversal
• Right/Left view of tree
• Minimum depth

Mental Trigger:

“Level-wise processing” → BFS

---

3. Binary Search Tree (BST) – Common

When to use:

• Tree follows ordering property

Keywords:

sorted, left < root < right

Core Idea:

Use property to eliminate half of tree at each step.

Typical Problems:

• Search in BST
• Validate BST
• Kth smallest element

Mental Trigger:

“Sorted tree” → BST logic

---

4. Tree Height / Diameter – Common

When to use:

• Maximum depth
• Longest path between nodes

Keywords:

height, depth, longest path

Core Idea:

Return subtree height from DFS.

For diameter:

diameter = leftHeight + rightHeight

Mental Trigger:

“Longest path” → DFS returning heights

---

5. LCA (Lowest Common Ancestor) – Common

When to use:

• Relationship between two nodes

Keywords:

ancestor, path, common

Core Idea:

If left subtree contains one node and right subtree contains the other → current node is LCA.

Advanced: Binary lifting for multiple queries.

Mental Trigger:

“Common ancestor of two nodes” → LCA pattern

---

6. Tree DP – Very Important

When to use:

• Node result depends on children
• Optimization problem on tree

Keywords:

subtree, child, combine

Core Idea:

Post-order traversal:

1. Solve left subtree
2. Solve right subtree
3. Combine results

Typical Problems:

• Maximum path sum
• House Robber III
• Diameter (also Tree DP)

Mental Trigger:

“Combine child results” → Tree DP

---

7. Segment Tree / BIT – Rare / Bonus

When to use:

• Frequent range queries + updates

Keywords:

range sum, update, query

Core Idea:

Precompute structure that answers queries in O(log n).

Typical Problems:

• Range sum queries
• Dynamic updates

Mental Trigger:

“Range query + updates” → Segment Tree

---

8. Trie – Common (Tree for Strings)

When to use:

• Prefix search problems

Keywords:

prefix, dictionary, search

Core Idea:

Store characters in tree structure for fast lookup.

Typical Problems:

• Autocomplete
• Word dictionary

Mental Trigger:

“Prefix-based lookup” → Trie

---

Golden Tree Problem Framework

Whenever solving a tree problem:

1. Decide traversal type (DFS or BFS).
2. Decide what each recursive call should return.
3. If optimizing → likely Tree DP.
4. If two nodes involved → think LCA.
5. If longest path → return heights.
6. If sorted property exists → use BST logic.
7. If range queries → Segment Tree.
8. If prefix strings → Trie.

---

Mini Notes / Tips

### Tips

- Most tree problems are DFS-based.
- If parent depends on children → Postorder traversal.
- Level-related problems → BFS.
- Two nodes relationship → LCA.
- Longest path → Height + Diameter logic.
- Always define: What should my recursive function return?
- Draw small tree examples before coding.