Path Sum Root to Leaf in Binary Tree in DSA Typescript - Deep Dive

Overview - Path Sum Root to Leaf in Binary Tree

What is it?

Path Sum Root to Leaf in a Binary Tree is a problem where you check if there is a path from the top of the tree (root) down to any bottom node (leaf) such that the numbers along that path add up to a given total. A binary tree is a structure where each node has up to two children. The goal is to find if any path's sum matches the target number.

Why it matters

This problem helps us understand how to explore all possible routes in a tree and check conditions along the way. Without this concept, we would struggle to solve many real-world problems like finding routes in maps, decision trees, or file system paths. It teaches how to combine tree traversal with condition checking, which is a foundation for many algorithms.

Where it fits

Before this, you should know what a binary tree is and how to traverse it (like depth-first search). After this, you can learn about more complex tree problems like path sums with constraints, or dynamic programming on trees.

Mental Model

Core Idea

Check every path from the root to a leaf to see if the sum of node values equals the target sum.

Think of it like...

Imagine walking from the entrance of a maze to any exit, adding up the numbers on the floor tiles you step on. You want to know if any path adds up to a specific number.

Root
  ├─ Left
  │    ├─ Left Leaf
  │    └─ Right Leaf
  └─ Right
       ├─ Left Leaf
       └─ Right Leaf

Each path from Root to Leaf is a sequence of nodes to sum.

Build-Up - 6 Steps

1

Foundation

Understanding Binary Tree Structure

Concept: Learn what a binary tree is and how nodes connect.

A binary tree has nodes where each node can have up to two children: left and right. The top node is called the root. Nodes without children are called leaves. Example: class TreeNode { val: number; left: TreeNode | null; right: TreeNode | null; constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) { this.val = val; this.left = left; this.right = right; } } This structure lets us build trees to explore paths.

Result

You can create and visualize binary trees with nodes and children.

Understanding the tree structure is essential because path sums depend on traversing from root to leaves.

2

Foundation

What is a Root-to-Leaf Path?

Concept: Define what a path from root to leaf means in a tree.

A root-to-leaf path starts at the root node and follows child links down until it reaches a leaf node (a node with no children). For example, in a tree: 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1 One root-to-leaf path is 5 -> 4 -> 11 -> 7.

Result

You can identify all root-to-leaf paths in a tree.

Knowing what counts as a path helps us decide which sums to check.

3

Intermediate

Traversing Tree to Find Path Sums

🤔Before reading on: do you think checking sums is easier with breadth-first or depth-first traversal? Commit to your answer.

Concept: Use depth-first search to explore each path and keep track of the sum so far.

We use a recursive function that visits each node, subtracting the node's value from the target sum. When we reach a leaf, we check if the remaining sum is zero. function hasPathSum(node: TreeNode | null, sum: number): boolean { if (!node) return false; if (!node.left && !node.right) return sum === node.val; return hasPathSum(node.left, sum - node.val) || hasPathSum(node.right, sum - node.val); } This checks all paths until one matches the sum.

Result

The function returns true if any root-to-leaf path sums to the target, false otherwise.

Depth-first search naturally fits path problems because it explores one path fully before backtracking.

4

Intermediate

Handling Edge Cases in Path Sum

🤔Before reading on: do you think an empty tree has a path sum? Commit to yes or no.

Concept: Consider cases like empty trees, single-node trees, and negative values.

If the tree is empty (null root), no path exists, so return false. If the tree has one node, check if its value equals the sum. Negative values can appear, so always subtract node values carefully. Example: hasPathSum(null, 0) // false hasPathSum(new TreeNode(5), 5) // true hasPathSum(new TreeNode(-2), -2) // true

Result

The function correctly handles all special cases without errors.

Thinking about edge cases prevents bugs and ensures your solution works for all inputs.

5

Advanced

Iterative Approach Using Stack

🤔Before reading on: do you think recursion or iteration is simpler for this problem? Commit to your answer.

Concept: Use a stack to simulate recursion and track sums iteratively.

Instead of recursion, use a stack to store pairs of nodes and the sum needed for the path. Example code: function hasPathSumIterative(root: TreeNode | null, sum: number): boolean { if (!root) return false; const stack: Array<[TreeNode, number]> = [[root, sum - root.val]]; while (stack.length > 0) { const [node, currSum] = stack.pop()!; if (!node.left && !node.right && currSum === 0) return true; if (node.right) stack.push([node.right, currSum - node.right.val]); if (node.left) stack.push([node.left, currSum - node.left.val]); } return false; } This avoids call stack limits.

Result

The iterative function returns true if a path sum exists, false otherwise.

Knowing iterative methods helps when recursion depth is a problem or when you want explicit control over traversal.

6

Expert

Optimizing with Early Stopping and Pruning

🤔Before reading on: do you think checking all paths is always necessary? Commit to yes or no.

Concept: Stop exploring paths as soon as the sum exceeds or cannot match the target to save time.

If node values are all positive, once the current sum exceeds the target, no need to continue down that path. Example: function hasPathSumPruned(node: TreeNode | null, sum: number): boolean { if (!node) return false; if (sum < node.val) return false; // prune if (!node.left && !node.right) return sum === node.val; return hasPathSumPruned(node.left, sum - node.val) || hasPathSumPruned(node.right, sum - node.val); } This reduces unnecessary checks in large trees.

Result

The function runs faster by skipping impossible paths early.

Pruning paths based on sum constraints can greatly improve performance in large or deep trees.

Under the Hood

The algorithm uses depth-first traversal, visiting nodes from root to leaves. At each node, it subtracts the node's value from the remaining sum needed. When it reaches a leaf, it checks if the remaining sum is zero, meaning the path sum matches. The recursion stack or explicit stack keeps track of the path state. This process explores all possible root-to-leaf paths systematically.

Why designed this way?

This approach was chosen because trees naturally fit recursive exploration. Checking sums on the fly avoids storing entire paths, saving memory. Alternatives like breadth-first search are possible but less intuitive for path problems. Early pruning was added to optimize performance when node values are positive, reducing unnecessary work.

Start
  ↓
[Root Node]
  ↓ subtract node.val from sum
  ├─ if leaf and sum == 0 → return true
  ├─ else explore left child
  └─ else explore right child
  ↓
Repeat until all paths checked or true found

Myth Busters - 3 Common Misconceptions

Quick: Does a path sum include partial paths that do not reach a leaf? Commit to yes or no.

Common Belief: Any path from root to any node counts for path sum, not just root to leaf.

Reality: Only paths that end at leaf nodes count for the path sum problem.

Why it matters: Counting partial paths leads to incorrect answers because the problem specifically requires full root-to-leaf paths.

Quick: Can negative numbers in nodes break the pruning optimization? Commit to yes or no.

Common Belief: Pruning paths when sum is exceeded always works regardless of node values.

Reality: Pruning only works safely if all node values are positive; negative values can make sums decrease later.

Why it matters: Using pruning blindly can cause missing valid paths when negative values exist.

Quick: Is iterative traversal always more efficient than recursion? Commit to yes or no.

Common Belief: Iterative solutions are always faster and better than recursive ones.

Reality: Recursive solutions are often simpler and just as efficient; iterative is useful mainly to avoid stack overflow.

Why it matters: Choosing iterative unnecessarily can complicate code without real benefit.

Expert Zone

1

When node values can be negative, pruning must be disabled or carefully adjusted to avoid missing valid paths.

2

Tracking the actual path (not just sum) requires extra memory and changes the algorithm to store nodes along the way.

3

In very deep trees, tail recursion optimization is not available in many languages, so iterative solutions prevent stack overflow.

When NOT to use

Avoid this approach if you need to find all paths with the sum, not just check existence. Instead, use backtracking to collect all paths. Also, if the tree is very large and memory is limited, consider iterative traversal with explicit stack to control memory usage.

Production Patterns

In real systems, this pattern is used in decision trees to check if a condition path exists, in file systems to find files with certain properties along the path, and in game AI to evaluate move sequences. Optimizations like pruning and iterative traversal are common in production to handle large data.

Connections

Depth-First Search (DFS)

Path sum checking builds directly on DFS traversal of trees.

Understanding DFS helps grasp how path sums are explored node by node.

Backtracking Algorithms

Path sum problems can be extended to backtracking when collecting all valid paths.

Knowing backtracking shows how to modify the problem to find all solutions, not just existence.

Route Planning in Transportation

Both involve finding paths with constraints (like cost or distance) in a network.

Seeing path sum as a cost check in route planning helps understand practical applications beyond trees.

Common Pitfalls

#1 Checking partial paths instead of root-to-leaf paths.

Wrong approach:

function hasPathSum(node: TreeNode | null, sum: number): boolean {
if (!node) return false;
if (sum === node.val) return true; // wrong: checks any node, not leaf
return hasPathSum(node.left, sum - node.val) || hasPathSum(node.right, sum - node.val);
}

Correct approach:

function hasPathSum(node: TreeNode | null, sum: number): boolean {
if (!node) return false;
if (!node.left && !node.right) return sum === node.val;
return hasPathSum(node.left, sum - node.val) || hasPathSum(node.right, sum - node.val);
}

Root cause:

Misunderstanding that only full root-to-leaf paths count, not partial paths.

#2 Applying pruning when node values can be negative.

Wrong approach:

function hasPathSumPruned(node: TreeNode | null, sum: number): boolean {
if (!node) return false;
if (sum < node.val) return false; // wrong if negatives exist
if (!node.left && !node.right) return sum === node.val;
return hasPathSumPruned(node.left, sum - node.val) || hasPathSumPruned(node.right, sum - node.val);
}

Correct approach:

function hasPathSum(node: TreeNode | null, sum: number): boolean {
if (!node) return false;
if (!node.left && !node.right) return sum === node.val;
return hasPathSum(node.left, sum - node.val) || hasPathSum(node.right, sum - node.val);
}

Root cause:

Assuming pruning works regardless of node values, ignoring negative numbers.

#3 Using recursion without base case for empty tree.

Wrong approach:

function hasPathSum(node: TreeNode | null, sum: number): boolean {
if (!node.left && !node.right) return sum === node.val;
return hasPathSum(node.left, sum - node.val) || hasPathSum(node.right, sum - node.val);
}

Correct approach:

function hasPathSum(node: TreeNode | null, sum: number): boolean {
if (!node) return false;
if (!node.left && !node.right) return sum === node.val;
return hasPathSum(node.left, sum - node.val) || hasPathSum(node.right, sum - node.val);
}

Root cause:

Forgetting to check if node is null before accessing properties.

Key Takeaways

Path Sum Root to Leaf checks if any path from the top to bottom of a binary tree adds up to a target number.

Depth-first search is the natural way to explore all root-to-leaf paths and track sums along the way.

Only full paths ending at leaves count; partial paths do not satisfy the problem requirements.

Pruning can speed up the search but only when node values are all positive.

Both recursive and iterative solutions work; choose based on tree size and environment constraints.

Practice

1. What does the "Path Sum Root to Leaf" problem ask you to find in a binary tree?

easy

A. The sum of all node values in the binary tree

B. If there exists a root-to-leaf path with a sum equal to a given target

C. The total number of nodes in the binary tree

D. The maximum depth of the binary tree

Solution

1. Step 1: Understand the problem statement

   The problem asks if there is any path from the root node down to any leaf node where the sum of the node values equals the target sum.

2. Step 2: Differentiate from other tree properties

   It is not about depth, total nodes, or sum of all nodes, but specifically about a path sum from root to leaf.

3. Final Answer:

   If there exists a root-to-leaf path with a sum equal to a given target -> Option B

4. Quick Check:

   Path sum means root-to-leaf sum = D [OK]

Hint: Focus on root-to-leaf paths, not entire tree sums [OK]

Common Mistakes:

• Confusing path sum with total tree sum
• Checking any path, not just root-to-leaf
• Ignoring leaf node condition

2. Which of the following TypeScript function signatures correctly represents a function to check path sum in a binary tree node defined as class TreeNode { val: number; left: TreeNode | null; right: TreeNode | null; }?

easy

A. function hasPathSum(root: number, sum: TreeNode): boolean

B. function hasPathSum(root: TreeNode, sum: string): boolean

C. function hasPathSum(root: TreeNode | null, sum: number): boolean

D. function hasPathSum(root: TreeNode | null): number

Solution

1. Step 1: Check parameter types

   The root should be a TreeNode or null (empty tree), and sum should be a number representing the target sum.

2. Step 2: Check return type

   The function returns a boolean indicating if such a path exists.

3. Final Answer:

   function hasPathSum(root: TreeNode | null, sum: number): boolean -> Option C

4. Quick Check:

   Correct types and return boolean = B [OK]

Hint: Root can be null; sum is number; return boolean [OK]

Common Mistakes:

• Swapping parameter types
• Using wrong return type
• Missing null for root parameter

3. Given the following binary tree and target sum = 22, what will the function hasPathSum(root, 22) return?

    5
   / \
  4   8
 /   / \
11  13  4
/  \      
7    2     1

medium

A. null

B. false

C. SyntaxError

D. true

Solution

1. Step 1: Identify root-to-leaf paths and their sums

   Check paths: 5->4->11->7 = 27, 5->4->11->2 = 22, 5->8->13 = 26, 5->8->4->1 = 18.

2. Step 2: Check if any path sum equals 22

   Path 5->4->11->2 sums to 22, so function returns true.

3. Final Answer:

   true -> Option D

4. Quick Check:

   Path sum 22 exists = true [OK]

Hint: Sum each root-to-leaf path, check for target [OK]

Common Mistakes:

• Ignoring leaf node condition
• Calculating sum incorrectly
• Confusing partial paths with full root-to-leaf

4. Consider this TypeScript code snippet for checking path sum:

function hasPathSum(root: TreeNode | null, sum: number): boolean {
  if (!root) return false;
  if (!root.left && !root.right) return root.val === sum;
  return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}

What does the function return if the tree is empty (root = null) and sum is 0?

medium

A. Returns false for empty tree and sum 0

B. Causes infinite recursion

C. Throws runtime error due to null access

D. Returns true incorrectly for non-empty tree

Solution

1. Step 1: Analyze base case for empty tree

   When root is null, if (!root) returns false immediately.

2. Step 2: Confirm for sum = 0

   Empty tree has no root-to-leaf path regardless of target sum, so false is correct.

3. Final Answer:

   Returns false for empty tree and sum 0 -> Option A

4. Quick Check:

   Null root always returns false [OK]

Hint: Empty tree always returns false [OK]

Common Mistakes:

• Thinking empty tree with sum 0 should return true
• Expecting runtime error without null check
• Confusing empty tree with single-node tree

5. You want to modify the path sum function to return all root-to-leaf paths where the sum equals the target. Which approach best solves this problem?

hard

A. Use DFS to track current path and sum, collect paths when sum matches at leaf

B. Use BFS and stop at first matching path

C. Use a queue to store sums only, ignoring paths

D. Return true or false immediately when sum matches any node

Solution

1. Step 1: Understand requirement to collect all matching paths

   We need to find all root-to-leaf paths whose sums equal the target, not just check existence.

2. Step 2: Choose traversal and tracking method

   DFS (depth-first search) allows tracking the current path and sum, and collecting paths when leaf and sum match.

3. Step 3: Evaluate other options

   BFS is less natural for path tracking; queues without paths lose information; returning boolean stops early.

4. Final Answer:

   Use DFS to track current path and sum, collect paths when sum matches at leaf -> Option A

5. Quick Check:

   DFS with path tracking = A [OK]

Hint: Track path and sum with DFS to collect all matching paths [OK]

Common Mistakes:

• Using BFS without path tracking
• Stopping at first match instead of collecting all
• Ignoring leaf node condition