Path Sum Root to Leaf in Binary Tree in DSA Typescript

Mental Model

We want to check if there is a path from the top of the tree to any bottom leaf where the numbers add up to a target sum.

Analogy: Imagine walking from the entrance of a maze to any exit, adding numbers on the path. We want to see if any path adds up exactly to a given number.

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

Dry Run Walkthrough

Input: tree: 5->4->11->7 (left leaf), target sum = 22

Goal: Find if any root-to-leaf path sums to 22

Step 1: start at root node 5, current sum needed = 22

5 (need 22)

Why: We begin from the top, checking if paths from here can reach sum 22

Step 2: go left to node 4, update needed sum to 22 - 5 = 17

5 -> 4 (need 17)

Why: Subtract current node value from target to track remaining sum

Step 3: go left to node 11, update needed sum to 17 - 4 = 13

5 -> 4 -> 11 (need 13)

Why: Continue subtracting node values along the path

Step 4: go left to node 7, update needed sum to 13 - 11 = 2

5 -> 4 -> 11 -> 7 (need 2)

Why: At leaf node, check if remaining sum equals node value

Step 5: 7 equals needed sum 2? No, backtrack and try right child of 11

5 -> 4 -> 11 -> 7 (need 2) backtrack

Why: Leaf node value does not match remaining sum, try other paths

Step 6: go right to node 2, update needed sum to 13 - 11 = 2

5 -> 4 -> 11 -> 2 (need 2)

Why: Check other leaf child for matching sum

Step 7: 2 equals needed sum 2? Yes, path found

5 -> 4 -> 11 -> 2 (need 2) success

Why: Leaf node value matches remaining sum, path sum exists

Result:

5 -> 4 -> 11 -> 2 -> null (path sum 22 found)

Annotated Code

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}

function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
  if (root === null) return false; // no node means no path

  // if leaf node, check if value equals targetSum
  if (root.left === null && root.right === null) {
    return root.val === targetSum;
  }

  // check left and right subtree with reduced sum
  return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
}

// Driver code to build tree and test
const root = new TreeNode(5,
  new TreeNode(4,
    new TreeNode(11,
      new TreeNode(7),
      new TreeNode(2)
    ),
    null
  ),
  new TreeNode(8,
    new TreeNode(13),
    new TreeNode(4, null, new TreeNode(1))
  )
);

console.log(hasPathSum(root, 22));

if (root === null) return false;

handle empty tree - no path exists

if (root.left === null && root.right === null) { return root.val === targetSum; }

at leaf, check if path sum matches target

return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);

recursively check left and right subtrees with updated sum

Output

true

Complexity Analysis

Time: O(n) because we visit each node once to check paths

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Compared to iterative BFS, recursion is simpler but uses call stack; BFS uses queue and similar time

Edge Cases

empty tree

returns false because no paths exist

DSA Typescript

if (root === null) return false;

single node tree where node value equals target sum

returns true because single node is leaf and matches sum

DSA Typescript

if (root.left === null && root.right === null) { return root.val === targetSum; }

single node tree where node value does not equal target sum

returns false because leaf value does not match sum

DSA Typescript

if (root.left === null && root.right === null) { return root.val === targetSum; }

When to Use This Pattern

When asked if a root-to-leaf path sums to a target, use recursion to subtract node values and check leaves.

Common Mistakes

Mistake: Checking sum only at root or non-leaf nodes instead of at leaf nodes
Fix: Only compare remaining sum to node value when at leaf nodes (no children)

Summary

Checks if any root-to-leaf path sums to a given target number.

Use when you need to verify if a path with a specific sum exists in a binary tree.

Subtract node values along the path and confirm at leaf nodes if the node value equals the remaining sum.

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