Path Sum Root to Leaf in Binary Tree in DSA C++

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 an exit, adding numbers on the path. 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 = 22 - 5 = 17

5 [curr], target sum left: 17

Why: We subtract root value from target to track remaining sum needed

Step 2: move to left child 4, current sum = 17 - 4 = 13

5 -> 4 [curr], target sum left: 13

Why: Continue down left path subtracting node values

Step 3: move to left child 11, current sum = 13 - 11 = 2

5 -> 4 -> 11 [curr], target sum left: 2

Why: Keep subtracting to track remaining sum

Step 4: move to left child 7, current sum = 2 - 7 = -5

5 -> 4 -> 11 -> 7 [curr], target sum left: -5

Why: Sum exceeded target, this path fails

Step 5: backtrack to 11, move to right child 2, current sum = 2 - 2 = 0

5 -> 4 -> 11 -> 2 [curr], target sum left: 0

Why: Found leaf with remaining sum zero, path matches target

Result:

5 -> 4 -> 11 -> 2 -> null
Answer: true (path sum exists)

Annotated Code

DSA C++

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

bool hasPathSum(TreeNode* root, int targetSum) {
    if (!root) return false; // empty tree no path
    if (!root->left && !root->right) return targetSum == root->val; // leaf check
    // check left and right subtrees with reduced sum
    return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);
}

int main() {
    // build tree from dry run example
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(4);
    root->right = new TreeNode(8);
    root->left->left = new TreeNode(11);
    root->left->left->left = new TreeNode(7);
    root->left->left->right = new TreeNode(2);
    root->right->left = new TreeNode(13);
    root->right->right = new TreeNode(4);
    root->right->right->right = new TreeNode(1);

    int targetSum = 22;
    cout << (hasPathSum(root, targetSum) ? "true" : "false") << endl;
    return 0;
}

if (!root) return false; // empty tree no path

handle empty tree base case

if (!root->left && !root->right) return targetSum == root->val; // leaf check

check if current node is leaf and sum matches

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

recurse left and right with reduced sum to find any valid path

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 may use more memory for wide trees

Edge Cases

empty tree

returns false because no path exists

DSA C++

if (!root) return false; // empty tree no path

single node tree where node value equals target sum

returns true because root is leaf and matches sum

DSA C++

if (!root->left && !root->right) return targetSum == root->val; // leaf check

single node tree where node value does not equal target sum

returns false because no matching path

DSA C++

if (!root->left && !root->right) return targetSum == root->val; // leaf check

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 for zero remainder.

Common Mistakes

Mistake: Checking sum at non-leaf nodes instead of only at leaves
Fix: Only return true if current node is leaf and remaining sum equals node value

Mistake: Not subtracting current node value from target sum before recursion
Fix: Pass targetSum - root->val to 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.

Subtract node values as you go down and confirm sum matches exactly at leaf nodes.