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.

Practice

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

easy

A. The total number of leaf nodes in the tree

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

C. The maximum depth of the binary tree

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

2. Step 2: Differentiate from other tree properties

   It is not about depth, counting leaves, or total sum, 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 check [OK]

Hint: Focus on root-to-leaf paths and their sums [OK]

Common Mistakes:

• Confusing path sum with total tree sum
• Checking sum for any path, not root-to-leaf
• Counting nodes instead of summing values

2. Which of the following C++ function signatures correctly represents a function to check path sum in a binary tree node structure?

easy

A. bool hasPathSum(TreeNode root, int targetSum)

B. int hasPathSum(TreeNode root, int targetSum)

C. void hasPathSum(TreeNode* root, int targetSum)

D. bool hasPathSum(TreeNode* root, int targetSum)

Solution

1. Step 1: Check parameter types and return type

   The function should take a pointer to the root node (TreeNode*) and an integer target sum, and return a boolean indicating if such a path exists.

2. Step 2: Validate each option

   bool hasPathSum(TreeNode* root, int targetSum) uses pointer and bool return type, which is correct. Options B and D pass TreeNode by value (less efficient), and B returns int, C returns void which is incorrect.

3. Final Answer:

   bool hasPathSum(TreeNode* root, int targetSum) -> Option D

4. Quick Check:

   Pointer input and bool output needed [OK]

Hint: Use pointer for tree nodes and bool for yes/no answers [OK]

Common Mistakes:

• Passing node by value instead of pointer
• Using wrong return type like void or int
• Missing pointer symbol (*) in parameter

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

#include <iostream>

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;
  if (!root->left && !root->right) return root->val == targetSum;
  return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);
}

int main() {
  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);

  bool result = hasPathSum(root, 22);
  std::cout << (result ? "true" : "false") << std::endl;
  return 0;
}

medium

A. true

B. false

C. Compilation error

D. Runtime error

Solution

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

   Check if any root-to-leaf path sums to 22. One path is 5->4->11->2 = 22.

2. Step 2: Confirm function logic and output

   The function correctly returns true if such a path exists. The code prints "true".

3. Final Answer:

   true -> Option A

4. Quick Check:

   Path 5+4+11+2 = 22 found [OK]

Hint: Check leaf paths sums carefully [OK]

Common Mistakes:

• Ignoring leaf node condition
• Subtracting values incorrectly
• Assuming no path matches without checking all

4. Identify the bug in the following code that attempts to check path sum in a binary tree:

bool hasPathSum(TreeNode* root, int targetSum) {
  if (root == nullptr) return false;
  if (root->left == nullptr && root->right == nullptr) return targetSum == root->val;
  return hasPathSum(root->left, targetSum) || hasPathSum(root->right, targetSum);
}

medium

A. The leaf node check should return false instead of comparison

B. The base case incorrectly returns false for nullptr

C. The targetSum is not reduced by root->val in recursive calls

D. The function should return int instead of bool

Solution

1. Step 1: Analyze recursive calls

   The function calls itself with the same targetSum without subtracting the current node's value, so it never reduces the sum along the path.

2. Step 2: Identify correct recursive logic

   It should call hasPathSum(root->left, targetSum - root->val) and similarly for right to correctly track remaining sum.

3. Final Answer:

   The targetSum is not reduced by root->val in recursive calls -> Option C

4. Quick Check:

   Subtract node value each step [OK]

Hint: Always subtract current node value from targetSum in recursion [OK]

Common Mistakes:

• Not updating targetSum in recursive calls
• Confusing base case return values
• Returning wrong data type

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

medium

A. No modification needed; the standard path sum check works for all values

B. Use a global variable to track sums instead of subtracting targetSum

C. Modify the function to return the maximum path sum instead of a boolean

D. Check all paths, not just root-to-leaf, because negative values can cancel out sums

Solution

1. Step 1: Consider negative values in path sum

   The standard recursive algorithm subtracts the current node's value (which can be negative) from the targetSum at each step, correctly handling negatives, zeros, and positives for root-to-leaf paths.

2. Step 2: No change required

   The problem is specifically for root-to-leaf paths, not arbitrary paths, so no modification is needed.

3. Final Answer:

   No modification needed; the standard path sum check works for all values -> Option A

4. Quick Check:

   Recursion handles negatives via subtraction [OK]

Hint: Standard path sum recursion works with negative node values [OK]

Common Mistakes:

• Thinking negatives require checking all paths
• Using global variables unnecessarily
• Changing return type without reason