CORE PATTERNVery High Frequency

Trees

A tree is a connected, acyclic graph with N nodes and N-1 edges. Binary trees are the most common — each node has at most two children. Tree problems are solved by DFS (pre/in/post-order) or BFS (level-order). Most solutions follow a recursive decomposition: solve for the left subtree, solve for the right subtree, combine.

TimeO(N)

SpaceO(H) — H = tree height

DifficultyEasy to Hard

Key Insight

Trust the recursion — solve left, solve right, combine.

Flip ⟲

Treesinorder BST

visit 1 (leftmost)

FLIP SIDETrees

Tap to flip back ⟲

RECOGNITION SIGNALS (WHEN TO USE THIS PATTERN)

✓Traverse or search a binary tree or BST

✓Compute height, depth, diameter, or path sum

✓Validate BST property or balance condition

✓Find the lowest common ancestor of two nodes

✓Serialize / deserialize a tree structure

✓Level-order processing — row by row

Types of Problems (Subpatterns)

Each subpattern solves a specific type of problem. Click on a card to view its template.

✓ SELECTED

DFS — Recursive Traversal

Pre / In / Post-order — choose the order based on when you need the parent vs children.

Binary Tree Inorder Traversal
Maximum Depth of Binary Tree
Path Sum

5 problems

BFS — Level-Order Traversal

Use a queue to process the tree row by row — ideal for level-specific questions.

Binary Tree Level Order Traversal
Binary Tree Right Side View
Average of Levels in Binary Tree

5 problems

Binary Search Tree Operations

Exploit BST ordering: left < node < right to search, insert, and validate in O(H).

Validate Binary Search Tree
Kth Smallest Element in a BST
Lowest Common Ancestor of a BST

5 problems

Lowest Common Ancestor

Post-order DFS: the LCA is the first node that finds both targets in different subtrees.

Lowest Common Ancestor of a Binary Tree
Lowest Common Ancestor of a BST
Lowest Common Ancestor of Deepest Leaves

5 problems

Tree Construction & Serialization

Rebuild a tree from traversal arrays or encode/decode it to a flat string.

Construct Binary Tree from Preorder and Inorder
Construct Binary Tree from Inorder and Postorder
Serialize and Deserialize Binary Tree

5 problems

Path Sum & Tree DP

Compute optimal values over all root-to-leaf or node-to-node paths with post-order DP.

Binary Tree Maximum Path Sum
Path Sum III
Sum Root to Leaf Numbers

5 problems

Iterative DFS (Explicit Stack)

Replace recursion with an explicit stack — required when recursion depth exceeds the call-stack limit.

Binary Tree Inorder Traversal (iterative)
Binary Tree Preorder Traversal (iterative)
Binary Tree Postorder Traversal (iterative)

5 problems

Template / Approach

Template for: DFS — Recursive Traversal

Approach

Base Case

Return immediately when node is nullptr — this is the natural recursion terminator.

Recurse on Children

Call the same function on node->left and node->right. Trust the recursion — assume they return the correct answer for their subtrees.

Combine and Return

Use the results from the left and right subtrees to compute the answer for the current node and return it upward.

Template

</>Common Template

💡Universal DFS skeleton. Place your logic before (pre-order), between (in-order), or after (post-order) the recursive calls depending on whether you need the parent before or after its children.

🔑

Key Idea:Trust the recursive contract: if dfs(left) and dfs(right) both return the correct answer for their subtrees, combining them at the current node is all that's needed. The base case (nullptr) provides the identity element (0 for height, true for balance, etc.).

1// DFS skeleton — adapt order as needed
2void dfs(TreeNode* node)
3{
4    if (!node) return;   // base case
5 
6    // PRE-ORDER:  process node BEFORE children
7    process(node);
8 
9    dfs(node->left);
10    dfs(node->right);
11 
12    // POST-ORDER: process node AFTER children
13    // process(node);
14}
15 
16// ── returning a value (e.g. height) ─────────────
17int height(TreeNode* node)
18{
19    if (!node) return 0;
20 
21    int leftH  = height(node->left);
22    int rightH = height(node->right);
23 
24    return 1 + max(leftH, rightH);   // combine
25}

4 if (!node) return; // base case

6 // PRE-ORDER: process node BEFORE children

7 process(node);

9 dfs(node->left);

10 dfs(node->right);

12 // POST-ORDER: process node AFTER children

13 // process(node);

14}

16// ── returning a value (e.g. height) ─────────────

17int height(TreeNode* node)

18{

19 if (!node) return 0;

21 int leftH = height(node->left);

22 int rightH = height(node->right);

24 return 1 + max(leftH, rightH); // combine

25}

Trees

RECOGNITION SIGNALS (WHEN TO USE THIS PATTERN)

Types of Problems (Subpatterns)

DFS — Recursive Traversal

BFS — Level-Order Traversal

Binary Search Tree Operations

Lowest Common Ancestor

Tree Construction & Serialization

Path Sum & Tree DP

Iterative DFS (Explicit Stack)

Template / Approach

Approach

Base Case

Recurse on Children

Combine and Return

Template

Practice Problems

Maximum Depth of Binary Tree

Invert Binary Tree

Diameter of Binary Tree

Path Sum

Balanced Binary Tree

Symmetric Tree

Binary Tree Level Order Traversal

Binary Tree Right Side View

Average of Levels in Binary Tree

Binary Tree Zigzag Level Order Traversal

Maximum Width of Binary Tree

Validate Binary Search Tree

Kth Smallest Element in a BST

Lowest Common Ancestor of a BST

Delete Node in a BST

Lowest Common Ancestor of a Binary Tree

Lowest Common Ancestor of Deepest Leaves

Maximum Difference Between Node and Ancestor

Construct Binary Tree from Preorder and Inorder Traversal

Serialize and Deserialize Binary Tree

Convert Sorted Array to Binary Search Tree

Flatten Binary Tree to Linked List

Binary Tree Maximum Path Sum

Path Sum III

Sum Root to Leaf Numbers

House Robber III

Binary Tree Inorder Traversal

Binary Tree Preorder Traversal

Recover Binary Search Tree

Trees

RECOGNITION SIGNALS (WHEN TO USE THIS PATTERN)

Types of Problems (Subpatterns)

DFS — Recursive Traversal

BFS — Level-Order Traversal

Binary Search Tree Operations

Lowest Common Ancestor

Tree Construction & Serialization

Path Sum & Tree DP

Iterative DFS (Explicit Stack)

Template / Approach

Approach

Base Case

Recurse on Children

Combine and Return

Template

Practice Problems

Maximum Depth of Binary Tree

Invert Binary Tree

Diameter of Binary Tree

Path Sum

Balanced Binary Tree

Symmetric Tree

Binary Tree Level Order Traversal

Binary Tree Right Side View

Average of Levels in Binary Tree

Binary Tree Zigzag Level Order Traversal

Maximum Width of Binary Tree

Validate Binary Search Tree

Kth Smallest Element in a BST

Lowest Common Ancestor of a BST

Delete Node in a BST

Lowest Common Ancestor of a Binary Tree

Lowest Common Ancestor of Deepest Leaves