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.