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 ⟲

Flip for Infographic

Interactive infographic on the flip side.

Click anywhere to Flip ⟲

FLIP SIDETrees

Click anywhere 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.

DFS — Recursive Traversal

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

Common Problems

• Binary Tree Inorder Traversal
• Maximum Depth of Binary Tree
• Path Sum
• Diameter of Binary Tree
• Invert Binary Tree

5 problems

BFS — Level-Order Traversal

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

Common Problems

• Binary Tree Level Order Traversal
• Binary Tree Right Side View
• Average of Levels in Binary Tree
• Maximum Width of Binary Tree
• Zigzag Level Order Traversal

5 problems

Binary Search Tree Operations

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

Common Problems

• Validate Binary Search Tree
• Kth Smallest Element in a BST
• Lowest Common Ancestor of a BST
• Convert Sorted Array to BST
• Delete Node in a BST

5 problems

Lowest Common Ancestor

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

Common Problems

• Lowest Common Ancestor of a Binary Tree
• Lowest Common Ancestor of a BST
• Lowest Common Ancestor of Deepest Leaves
• Kth Ancestor of a Tree Node
• Maximum Difference Between Node and Ancestor

5 problems

Tree Construction & Serialization

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

Common Problems

• Construct Binary Tree from Preorder and Inorder
• Construct Binary Tree from Inorder and Postorder
• Serialize and Deserialize Binary Tree
• Convert Sorted Array to Binary Search Tree
• Flatten Binary Tree to Linked List

5 problems

Path Sum & Tree DP

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

Common Problems

• Binary Tree Maximum Path Sum
• Path Sum III
• Sum Root to Leaf Numbers
• Longest Univalue Path
• House Robber III

5 problems

Iterative DFS (Explicit Stack)

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

Common Problems

• Binary Tree Inorder Traversal (iterative)
• Binary Tree Preorder Traversal (iterative)
• Binary Tree Postorder Traversal (iterative)
• Flatten Binary Tree to Linked List
• Recover Binary Search Tree

5 problems

Template / Approach

Template for: DFS — Recursive Traversal

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_cpp

💡 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.

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}

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.).

Practice Problems

Sharpen your skills with hand-picked problems.

View All Problems

Easy

Maximum Depth of Binary Tree

LeetCode #104

Easy

Invert Binary Tree

LeetCode #226

Easy

Diameter of Binary Tree

LeetCode #543

Easy

Path Sum

LeetCode #112

Easy

Balanced Binary Tree

LeetCode #110

Easy

Symmetric Tree

LeetCode #101

Medium

Binary Tree Level Order Traversal

LeetCode #102

Medium

Binary Tree Right Side View

LeetCode #199

Easy

Average of Levels in Binary Tree

LeetCode #637

Medium

Binary Tree Zigzag Level Order Traversal

LeetCode #103

Medium

Maximum Width of Binary Tree

LeetCode #662

Medium

Validate Binary Search Tree

LeetCode #98

Medium

Kth Smallest Element in a BST

LeetCode #230

Medium

Lowest Common Ancestor of a BST

LeetCode #235

Medium

Delete Node in a BST

LeetCode #450

Medium

Lowest Common Ancestor of a Binary Tree

LeetCode #236

Medium

Lowest Common Ancestor of Deepest Leaves

LeetCode #1123

Medium

Maximum Difference Between Node and Ancestor

LeetCode #1026

Medium

Construct Binary Tree from Preorder and Inorder Traversal

LeetCode #105

Hard

Serialize and Deserialize Binary Tree

LeetCode #297

Easy

Convert Sorted Array to Binary Search Tree

LeetCode #108

Medium

Flatten Binary Tree to Linked List

LeetCode #114

Hard

Binary Tree Maximum Path Sum

LeetCode #124

Medium

Path Sum III

LeetCode #437

Medium

Sum Root to Leaf Numbers

LeetCode #129

Medium

House Robber III

LeetCode #337

Easy

Binary Tree Inorder Traversal

LeetCode #94

Easy

Binary Tree Preorder Traversal

LeetCode #144

Medium

Recover Binary Search Tree

LeetCode #99

Trees

1// DFS skeleton — adapt order as needed

2void dfs(TreeNode* node)

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}