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

Concept Flow - Path Sum Root to Leaf in Binary Tree

Start at root node

↓

Check if node is null?

Yes→Return false

No↓

Check if leaf node?

Yes→Check if sum equals target

↓

Return true/false

↓

Recurse left with updated sum

↓

Recurse right with updated sum

↓

Return left_result OR right_result

Start from root, check if node is leaf and sum matches target, else recurse left and right with updated sum, return true if any path matches.

Execution Sample

DSA Javascript

function hasPathSum(node, sum) {
  if (!node) return false;
  if (!node.left && !node.right) return sum === node.val;
  return hasPathSum(node.left, sum - node.val) || hasPathSum(node.right, sum - node.val);
}

Checks if any root-to-leaf path sums to the target value.

Execution Table

Step	Operation	Current Node	Sum Remaining	Return Value	Visual Tree State
1	Start at root	5	22	?	5 / \ 4 8 / / \ 11 13 4 / \ 7 2 1
2	Check leaf?	5	22	No	Same
3	Recurse left	4	17	?	Same
4	Check leaf?	4	17	No	Same
5	Recurse left	11	13	?	Same
6	Check leaf?	11	13	No	Same
7	Recurse left	7	2	?	Same
8	Check leaf?	7	2	Yes	Same
9	Compare sum	7	2	False	Same
10	Recurse right	2	2	?	Same
11	Check leaf?	2	2	Yes	Same
12	Compare sum	2	2	True	Same
13	Return true up	11	13	True	Same
14	Return true up	4	17	True	Same
15	Return true up	5	22	True	Same
16	Stop	N/A	N/A	True	Final: Path 5->4->11->2 sums to 22

💡 Found a root-to-leaf path with sum 22, so returns true.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	After Step 10	Final
node	5	4	11	7	2	N/A
sum_remaining	22	17	13	2	2	N/A
return_value	?	?	?	?	?	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. The check at step 8 and 11 ensures we only compare sums when at a leaf node, as shown in execution_table rows 8-12.

Why do we subtract node.val from sum when recursing?

We reduce the target sum by the current node's value to track how much is left to reach the target. This is seen in the sum_remaining column updating at steps 3, 5, 7, and 10.

What happens if the node is null?

The function returns false immediately (step 2), meaning no path exists through a null node.

Visual Quiz - 3 Questions

Look at the execution_table at step 11, what is the sum_remaining value?

A 13

B 17

C 2

D 22

💡 Hint

Check the 'Sum Remaining' column at step 11 in the execution_table.

At which step does the function find a valid path sum and return true?

A Step 12

B Step 14

C Step 9

D Step 16

💡 Hint

Look for the first 'Compare sum' operation returning true in the execution_table.

If the target sum was 26 instead of 22, what would happen at step 12?

A Return true because sum matches

B Return false because sum does not match

C Recurse further left

D Return false because node is null

💡 Hint

At step 12, the sum comparison depends on sum_remaining matching node.val exactly.

Concept Snapshot

function hasPathSum(node, sum)
- Return false if node is null
- If leaf node, check sum === node.val
- Else recurse left and right with sum - node.val
- Return true if any path matches
- Finds if root-to-leaf path sums to target

Full Transcript

This visualization shows how the path sum check works in a binary tree. Starting at the root, the function checks if the node is null, returning false if so. If the node is a leaf, it compares the remaining sum to the node's value. If they match, it returns true. Otherwise, it recurses down left and right children, subtracting the current node's value from the sum. The execution table traces each step, showing the current node, remaining sum, and return values. The variable tracker shows how node and sum_remaining change. Key moments clarify why leaf checks and sum subtraction are needed. The quiz tests understanding of sum tracking and return points. This method efficiently finds if any root-to-leaf path equals the target sum.