Path Sum Root to Leaf in Binary Tree in DSA Javascript

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 down a tree from the top branch to the bottom leaves, adding numbers on each branch. We want to see if any path adds up exactly to a certain 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 is 22

5 (need 22)

Why: We begin at the top and want to find a path that sums to 22

Step 2: go left to node 4, subtract 5 from sum, now need 17

5 -> 4 (need 17)

Why: We move down left, reducing the sum by the current node's value

Step 3: go left to node 11, subtract 4 from sum, now need 13

5 -> 4 -> 11 (need 13)

Why: Continue down left path, updating needed sum

Step 4: go left to node 7, subtract 11 from sum, now need 2

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

Why: Move to leaf candidate, update sum needed

Step 5: node 7 is leaf, check if needed sum is 7

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

Why: Leaf node must match remaining sum to confirm path

Step 6: needed sum 2 ≠ 7, backtrack to node 11 and try right child 2

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

Why: Left leaf failed, try sibling leaf

Step 7: node 2 is leaf, check if needed sum is 2

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

Why: Leaf node must match remaining sum

Step 8: needed sum 2 = 2, path found

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

Why: Sum matches at leaf, success

Result:

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

Annotated Code

DSA Javascript

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function hasPathSum(root, targetSum) {
  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;
  }

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

// driver code
const root = new TreeNode(5,
  new TreeNode(4,
    new TreeNode(11,
      new TreeNode(7),
      new TreeNode(2)
    )
  ),
  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 node as no path

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

check if leaf node value matches remaining sum

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

recurse left and right with updated sum, return true if any path matches

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 with queue, recursion is simpler but uses call stack; BFS uses extra queue memory

Edge Cases

empty tree

returns false because no path exists

DSA Javascript

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 Javascript

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 Javascript

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 recursive depth-first search subtracting node values from the target.

Common Mistakes

Mistake: Checking sum only at root or non-leaf nodes
Fix: Check sum only when reaching leaf nodes to confirm full path sum

Mistake: Not subtracting current node value from target sum before recursion
Fix: Subtract current node's value from target sum before recursive calls

Summary

Checks if any root-to-leaf path sums to a given target in a binary tree.

Use when you need to verify if a path with a specific sum exists from top to bottom.

The key is to subtract node values from the target sum as you go down and check only at leaves.

Practice

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

easy

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

B. The maximum depth of the binary tree

C. The total number of nodes in the binary tree

D. The sum of all node values in 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 a given target sum.

2. Step 2: Differentiate from other tree properties

   This is different from finding depth, counting nodes, or summing all nodes. It specifically checks for 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 A

4. Quick Check:

   Path sum problem = Check root-to-leaf sum [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 root-to-leaf
• Ignoring leaf node condition

2. Which of the following is the correct base case check in JavaScript for a null node in a recursive path sum function?

easy

A. if (node === null) return true;

B. if (node == undefined) return true;

C. if (node === undefined) return null;

D. if (node === null) return false;

Solution

1. Step 1: Identify base case for recursion

   When the current node is null, it means no path exists here, so return false to indicate failure to find the path.

2. Step 2: Check JavaScript strict equality and return value

   Using 'node === null' is correct to check null nodes, and returning false means no valid path found.

3. Final Answer:

   if (node === null) return false; -> Option D

4. Quick Check:

   Null node means no path = false [OK]

Hint: Return false on null node to stop recursion [OK]

Common Mistakes:

• Returning true on null node
• Using == instead of ===
• Returning null instead of boolean

3. What will be the output of the following code snippet?

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

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

const root = new TreeNode(5, new TreeNode(4, new TreeNode(11, new TreeNode(7), new TreeNode(2))), new TreeNode(8, null, new TreeNode(4, null, new TreeNode(1))));
console.log(hasPathSum(root, 22));

medium

A. true

B. false

C. undefined

D. TypeError

Solution

1. Step 1: Trace the path sums in the tree

   Check if any root-to-leaf path sums to 22. The path 5->4->11->2 sums to 22 (5+4+11+2=22).

2. Step 2: Evaluate the recursive calls

   The function returns true because the path exists, so console.log prints true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Path 5-4-11-2 sum=22 = true [OK]

Hint: Check leaf paths sums carefully to confirm true [OK]

Common Mistakes:

• Ignoring leaf node condition
• Miscomputing sum along path
• Assuming false when path exists

4. Find the bug in this JavaScript function for path sum and select the fix:

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

medium

A. Change 'node === null' to 'node == null' in base case

B. Remove the leaf node check entirely

C. Change 'sum = node.val' to 'sum === node.val' in the leaf check

D. Change '||' to '&&' in the return statement

Solution

1. Step 1: Identify incorrect assignment in leaf check

   The line 'return sum = node.val;' uses assignment '=' instead of comparison '===' which causes wrong behavior.

2. Step 2: Correct the comparison operator

   Replace '=' with '===' to properly check if sum equals node.val at leaf nodes.

3. Final Answer:

   Change 'sum = node.val' to 'sum === node.val' in the leaf check -> Option C

4. Quick Check:

   Use '===' for comparison, not '=' [OK]

Hint: Use '===' for equality checks, not '=' assignment [OK]

Common Mistakes:

• Using '=' instead of '===' in conditions
• Removing necessary base cases
• Changing logical operators incorrectly

5. Given a binary tree where node values can be negative, which modification is necessary to correctly check for a path sum equal to target?

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

hard

A. Use absolute values of node.val and sum in comparisons

B. No change needed; current code works with negative values

C. Change base case to return true if sum <= node.val

D. Add a visited set to avoid infinite loops with negative values

Solution

1. Step 1: Understand negative values impact

   The current recursive approach subtracts node values from sum and checks leaf equality, which works even if values are negative.

2. Step 2: Confirm no cycles in binary tree

   Binary trees have no cycles, so no infinite loops occur; no visited set needed.

3. Final Answer:

   No change needed; current code works with negative values -> Option B

4. Quick Check:

   Negative values handled by subtraction correctly [OK]

Hint: Binary trees have no cycles; negative values handled naturally [OK]

Common Mistakes:

• Adding unnecessary visited sets
• Changing base case incorrectly
• Using absolute values which breaks logic