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.