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.