Path Sum Root to Leaf in Binary Tree in DSA C++ - Execution Trace

Concept Flow - Path Sum Root to Leaf in Binary Tree

Start at root node

↓

Check if node is leaf?

↓

Sum == target?

↓

Go right child

↓

Return True

↓

Return result

Start from root, check if leaf and sum matches target. If not leaf, go left and right recursively, combine results.

Execution Sample

DSA C++

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);
}

Checks if any root-to-leaf path sums to targetSum by recursively subtracting node values.

Execution Table

Step	Operation	Current Node	Target Sum Remaining	Leaf Check	Return Value	Visual State
1	Start at root	5	22	No	N/A	5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1
2	Go left child	4	17	No	N/A	4 / 11 / 7
3	Go left child	11	13	No	N/A	11 / \ 7 2
4	Go left child	7	2	Yes	False	7 (leaf)
5	Go right child	2	2	Yes	True	2 (leaf)
6	Return from 11	11	13	No	True	11 subtree returns True
7	Return from 4	4	17	No	True	4 subtree returns True
8	Return from root	5	22	No	True	Whole tree returns True

💡 Returned True at leaf node with path sum matching target (5->4->11->2 = 22)

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
Current Node	5	4	11	7	2	11	4	5
Target Sum Remaining	22	17	13	2	2	13	17	22
Return Value	N/A	N/A	N/A	False	True	True	True	True

Key Moments - 3 Insights

Why do we check if the node is a leaf before comparing sums?

Because only root-to-leaf paths count. See Step 4 and 5 where leaf nodes 7 and 2 are checked for sum equality.

Why do we subtract the current node's value from targetSum when going deeper?

To keep track of the remaining sum needed. At Step 3, targetSum is 13 after subtracting 5 and 4.

Why do we return the OR of left and right subtree results?

Because if any path matches, we return True. At Step 6 and 7, left subtree returns True, so whole returns True.

Visual Quiz - 3 Questions

Look at the execution table, what is the target sum remaining when visiting node 11 at Step 3?

A 13

B 17

C 22

D 2

💡 Hint

Check the 'Target Sum Remaining' column at Step 3 in the execution table.

At which step does the function first return True?

A Step 4

B Step 5

C Step 6

D Step 7

💡 Hint

Look at the 'Return Value' column; Step 5 shows True at a leaf node.

If the left subtree did not have a path sum matching target, what would happen at Step 7?

A Return True immediately

B Skip right subtree

C Return False and check right subtree

D Return True only if right subtree matches

💡 Hint

See how the OR operation combines left and right subtree results in the code and execution table.

Concept Snapshot

Path Sum Root to Leaf in Binary Tree:
- Check if current node is leaf and sum matches target
- Recursively check left and right children with updated sum
- Return true if any path matches
- Use OR to combine left/right results
- Base case: null node returns false

Full Transcript

This visualization shows how the path sum check works in a binary tree. Starting at the root node with target sum 22, we recursively subtract node values as we go down. When we reach a leaf node, we check if the remaining sum equals the leaf's value. If yes, we return true. The recursion combines results from left and right subtrees using OR. The example tree has a path 5->4->11->2 that sums to 22, so the function returns true. Variables like current node and remaining sum update at each step, and return values propagate back up the call stack.

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