PATTERN 11: Trees (Binary Tree + BST)

D

Qubits of DPK

April 11, 2026

Core DSA
Pattern 11 is where recursion becomes structural, not optional.
If Pattern 10 was decision trees,
Pattern 11 is data-structure-driven recursion.

Core Idea (lock this)

“Every tree problem is: solve left subtree, solve right subtree, combine.”
You don’t traverse trees.
You return information upward.

How to Recognize This Pattern (CRITICAL)

Think Tree Recursion when:
  • Input is a tree (binary / BST)
  • Each node’s answer depends on children
  • DFS feels natural
  • You hear:
If you’re passing values downward blindly →
If you’re returning results upward →

30 MUST-DO INTERVIEW PROBLEMS

(10 Easy → 10 Medium → 10 Hard)

EASY (1–10): Tree Traversal & Basics

Goal: remove fear of tree recursion.
  1. #
    Binary Tree Inorder Traversal – LC 94
  2. #
    Binary Tree Preorder Traversal – LC 144
  3. #
    Binary Tree Postorder Traversal – LC 145
  4. #
    Maximum Depth of Binary Tree – LC 104
  5. #
    Same Tree – LC 100
  6. #
    Symmetric Tree – LC 101
  7. #
    Search in a Binary Search Tree – LC 700
  8. #
    Minimum Depth of Binary Tree – LC 111
  9. #
    Path Sum – LC 112
  10. #
    Convert Sorted Array to BST – LC 108
After these:
You should visualize recursion

️ MEDIUM (11–20): Return Values from Subtrees

English explanation first: what does each recursive call return?
  1. #
    Balanced Binary Tree – LC 110
  2. #
    Diameter of Binary Tree – LC 543
  3. #
    Lowest Common Ancestor of Binary Tree – LC 236
  4. #
    Validate Binary Search Tree – LC 98
  5. #
    Binary Tree Right Side View (DFS version) – LC 199
  6. #
    Path Sum II – LC 113
  7. #
    Count Complete Tree Nodes – LC 222
  8. #
    Sum Root to Leaf Numbers – LC 129
  9. #
    Binary Tree Paths – LC 257
  10. #
    Delete Node in a BST – LC 450
Interview focus:
Can you explain

HARD (21–30): Multiple Values & Global State

These test clarity under recursion pressure.
  1. #
    Binary Tree Maximum Path Sum – LC 124
  2. #
    Serialize and Deserialize Binary Tree – LC 297
  3. #
    Recover Binary Search Tree – LC 99
  4. #
    Construct Binary Tree from Preorder and Inorder – LC 105
  5. #
    Construct Binary Tree from Inorder and Postorder – LC 106
  6. #
    Count Nodes Equal to Sum of Descendants – LC 1973
  7. #
    Longest Univalue Path – LC 687
  8. #
    Path Sum III – LC 437
  9. #
    Binary Tree Cameras – LC 968
  10. #
    House Robber III – LC 337
These require:
  • Returning multiple values
  • Global vs local state control
  • Careful handling of nulls

THE QUESTION YOU MUST ASK BEFORE CODING

For every tree problem, ask:
“What should my recursive function return?”
If you can’t answer that → stop.

Common Interview Killers

  • Confusing height vs depth
  • Using global variables blindly
  • Not handling null nodes
  • Traversing when return-value logic is required

INTERVIEW REVISION CARD — Pattern 11

1️⃣ Pattern in One Line

"Every tree problem = solve left subtree + solve right subtree + combine results upward."

2️⃣ Recognize It When...

  • Input is a binary tree or BST
  • Each node's answer depends on its children
  • Trigger words: "height", "depth", "balanced", "path", "ancestor", "diameter"
  • DFS feels natural — process children before parent

3️⃣ Don't Confuse With...

  • Backtracking (P10) → backtracking undoes choices; tree recursion never undoes
  • Graph DFS (P14A) → graphs have cycles; trees are acyclic with parent-child structure
  • BFS (P14B) → BFS for level-order; DFS for depth-based tree problems

4️⃣ Approach in 3 Steps

  1. #
    Ask: "What should my recursive function RETURN?" — define this first
  2. #
    Solve for left and right subtrees independently
  3. #
    Combine results at current node and return upward

5️⃣ Invariant to Maintain

"Every recursive call returns exactly the information needed by its parent — nothing more, nothing less."

6️⃣ Complexity to Justify

  • Time: O(N) — visit each node exactly once
  • Space: O(H) recursion stack — H = height = O(log N) balanced, O(N) skewed
  • Why: Each node processed once in post-order fashion

7️⃣ Edge Cases to Always Check

  • Null root (empty tree)
  • Single node tree
  • Skewed tree (all left or all right)
  • Negative values in path sum problems
  • BST with duplicate values

8️⃣ One Line to Say in Interview

"I'll define what each recursive call returns, solve left and right subtrees independently, then combine at the current node — O(N) time, O(H) space."