Pattern GuideBinary Tree & Subtree Recursion
Data Structure Pattern

Binary Tree & Subtree Recursion

"Every node is the root of its own subtree. Solve the subtree, solve the tree."

12 min read
Fundamental
Time: O(N)
01
THE RECURSIVE RELATION

The Subtree Principle

🌳

A binary tree is not just a collection of nodes pointing to each other. The magic of trees is in their mathematical definition: a tree is either empty, or it is a root node pointing to two other binary trees (left subtree and right subtree).

This recursive structure implies a powerful recurrence relation. If you need to compute a property for a node, the formula is almost always:

Result(Node) = Combine(Result(Node.Left), Result(Node.Right), Node.Val)

To solve binary tree problems, you must force a mental shift: Stop trying to visualize the entire tree. Focus on only one local node and trust that the recursive calls on your children will return the correct subtree answers.

THE SUBTREE RULE OF THUMB
If you are stuck on a tree problem, ask yourself: "If I were a leaf node, what is my base case? If my left and right children handed me their completed answers, what operations would I do to combine them and return my answer?"
02
TRAVERSAL DESIGN

Deciding Traversal Order (Pre vs In vs Post)

The definitions are straightforward: Pre-order visits the parent node first, In-order visits the left child then parent then right child, and Post-order visits both children before the parent. However, knowing these sequence definitions alone will not help you solve tree problems. To solve actual algorithmic challenges, you must visualize the data dependency—how information flows through the call stack—to know which order your problem demands:

Pre-Order (Top-Down / Parent-First)

Parent → Children

You process the current node before visiting its children. This allows you to establish context or calculate values at the parent level, then pass those computed values down as parameters in the recursive function calls.

When to use: When children require parent context to decide their own outcome. For example, if you are tracking the total sum of node values along a path from the root down to a leaf node, a child node cannot calculate its own path sum unless the parent calculates and passes down the running sum of all ancestor nodes visited so far. Similarly, when building a list of paths from the root, parent nodes must append their values to a list before passing that list down so children can continue building on top of it.

Simple Example: Passing accumulated state down as arguments:dfs(node.left, currentSum + node.val);

Post-Order (Bottom-Up / Child-First)

Children → Parent

You process the current node after getting results back from both children. Information propagates upward from the leaf nodes back to the root via return values.

When to use: When the current node cannot resolve the query on its own. For example, to calculate Tree Height, a parent node cannot know its own height until both of its children have evaluated and returned theirs. The parent then aggregates these results by taking the maximum height of its subtrees and adding 1. This is the primary choice for aggregations like diameter, subtree balance checks, or Lowest Common Ancestor (LCA).

Simple Example: Collecting and returning child values:let leftVal = dfs(node.left);
let rightVal = dfs(node.right);
return combine(leftVal, rightVal, node.val);

In-Order (BST Sorting / Left-to-Right)

Left → Parent → Right

You visit the left subtree, process the parent node, then visit the right subtree.

When to use: Almost exclusively used for Binary Search Trees (BSTs) because it visits nodes in perfectly sorted order, or in expression trees (infix notation).

BFS (Level Order / Layer-by-Layer)

Row-by-Row Queue

You explore the tree horizontally layer-by-layer rather than diving deep.

When to use: When the problem specifically mentions tree levels, grouping elements by row, vertical columns, or finding the shortest distance (e.g. zigzag, side view).

03
VISUAL DEMO

Interactive Traversal Simulator

Choose a traversal strategy to watch the path of execution, the active state, and trace how the helper data structures manage nodes.

12345
Step 0 / 5
Ready to start. Stack will store nodes waiting to be processed.
Visited List:
[]
stack:
[]
04
BLUEPRINTS

Implementation Blueprints

Here are standard, copy-pasteable layout codes for writing tree recursions. Switch tabs to see your preferred programming language.

1. DFS Bottom-Up Blueprint (Child-First / Post-Order)

How it Works

  • Perfect when parent depends on children results.
  • Base case checks if node is null (returns 0 or default values).
  • Makes recursive calls on left and right subtrees.
  • Combines the child answers inside the current frame.
dfsBottomUp.js
1
function maxDepth(root) {
2
// 1. Base Case: An empty node contributes 0 to depth
3
if (root === null) return 0;
4
5
// 2. Recurse: Get depth of left and right subtrees
6
let leftDepth = maxDepth(root.left);
7
let rightDepth = maxDepth(root.right);
8
9
// 3. Process: Current node adds 1 to the maximum child depth
10
// This is post-order (bottom-up), as we need children answers first!
11
return Math.max(leftDepth, rightDepth) + 1;
12
}

2. DFS Top-Down Blueprint (Parent-First / Pre-Order)

How it Works

  • Perfect when children depend on values passed down from parent.
  • Update context (running sum, path array) as you move down.
  • Base case checks null, leaf node check validates final condition.
  • Recursively call down to kids, propagating intermediate results.
dfsTopDown.js
1
function hasPathSum(root, targetSum) {
2
// 1. Base Case: If root is null, path sum is impossible
3
if (root === null) return false;
4
5
// 2. Process: Subtract current node value from running targetSum
6
let remainingSum = targetSum - root.val;
7
8
// 3. Check condition at leaf node (Top-Down check)
9
if (root.left === null && root.right === null) {
10
return remainingSum === 0;
11
}
12
13
// 4. Recurse: Propagate the decision down to subtrees (Pre-Order style)
14
return hasPathSum(root.left, remainingSum) ||
15
hasPathSum(root.right, remainingSum);
16
}

3. BFS Level Order Blueprint (Layer-by-layer / Queue)

How it Works

  • Process rows horizontally.
  • Use a queue to track visitation list.
  • An inner loop of size levelSize processes one complete layer in a single step.
  • Children are enqueued at the back to be resolved in subsequent iterations.
bfsLevelOrder.js
1
function levelOrder(root) {
2
if (root === null) return [];
3
4
let result = [];
5
// 1. Initialize queue with root
6
let queue = [root];
7
8
while (queue.length > 0) {
9
let levelSize = queue.length;
10
let currentLevel = [];
11
12
// 2. Process all nodes in the current layer/level
13
for (let i = 0; i < levelSize; i++) {
14
let node = queue.shift();
15
currentLevel.push(node.val);
16
17
// 3. Enqueue children for the next level
18
if (node.left !== null) queue.push(node.left);
19
if (node.right !== null) queue.push(node.right);
20
}
21
22
// 4. Add layer result
23
result.push(currentLevel);
24
}
25
26
return result;
27
}
05
CAUTION

Common Pitfalls

Forgetting null Check

If you do not check if (root === null) at the top, calling root.left will throw a Null Pointer Exception immediately. Always guard your base cases first.

Call Stack Overflow

For highly skewed/unbalanced trees (like a straight line of nodes), recursive DFS uses O(N) call stack memory instead of O(log N). In interviews, state this edge case and mention how Iterative DFS or Morris Traversal solves it.

06
APPLICATIONS

Real-world Tree Problems

1. Maximum Depth of a Binary Tree (Post-Order / Bottom-Up)

Problem: Find the length of the longest path from root to leaf.
Core Logic: You cannot calculate the height of the current node until you receive the heights of both the left and right subtrees. This makes it a perfect candidate for a Bottom-Up (Post-Order) search.
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;

2. Root-to-Leaf Path Sum (Pre-Order / Top-Down)

Problem: Determine if the tree has a root-to-leaf path where summing all values equals a target value.
Core Logic: The parent passes down the remaining target sum after subtracting its own value. When the traversal reaches a leaf node, it checks if the remaining target sum has reached exactly 0. This is a Top-Down (Pre-Order) propagation.
return dfs(root.left, target - root.val) || dfs(root.right, target - root.val);

3. Validate Binary Search Tree (In-Order)

Problem: Check if a binary tree satisfies the BST property (all left nodes < root < all right nodes).
Core Logic: Since an in-order traversal of a valid BST always yields values in strictly increasing order, we can check this property dynamically by tracking the value of the previously visited node during an in-order traversal.
if (prev !== null && root.val <= prev.val) return false;
prev = root; // update predecessor node

4. Right-Side View of a Tree (BFS / Level Order)

Problem: Return the nodes that are visible when looking at the tree from the right side.
Core Logic: We perform a standard level-order BFS. At each level, the last node processed in the layer queue represents the right-most node visible at that horizontal row depth.
// inside BFS level loop:
if (i === levelSize - 1) rightViewList.push(node.val);

07
PRACTICE

Ready to Practice?

Maximum Depth of Binary TreeEasy
Binary Tree Level Order TraversalMedium
BST Search & In-orderEasy
Diameter of Binary TreeEasy

"Every node is a root. Solve the children first, or pass the parent state down."