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

Concept Flow - Path Sum Root to Leaf in Binary Tree

Start at root node

↓

Check if node is leaf

↓

Check if sum == node.Val

↓

Go to right child

↓

Return True

↓

Return False if no path found

Start from the root, check if current node is a leaf and if the remaining sum equals node's value. If yes, path found. Otherwise, recursively check left and right children with updated sum.

Execution Sample

DSA Go

func hasPathSum(root *TreeNode, sum int) bool {
  if root == nil {
    return false
  }
  if root.Left == nil && root.Right == nil {
    return sum == root.Val
  }
  return hasPathSum(root.Left, sum-root.Val) || hasPathSum(root.Right, sum-root.Val)
}

Checks if there is a root-to-leaf path in the binary tree where the sum of node values equals the target sum.

Execution Table

Step	Operation	Current Node Value	Remaining Sum	Action	Visual State
1	Start at root	5	22	Check leaf? No, go left	5 / \ 4 8
2	Go left	4	17	Check leaf? No, go left	5 / \ 4 8 / / \ 11 13 4
3	Go left	11	13	Check leaf? No, go left	5 / \ 4 8 / / \ 11 13 4 / \ 7 2
4	Go left	7	2	Check leaf? Yes, sum==val? No	Leaf 7 checked, no match
5	Back to 11, go right	2	2	Check leaf? Yes, sum==val? Yes	Leaf 2 checked, match found
6	Return True	-	-	Path found: 5->4->11->2	Path sum 22 found
7	Stop	-	-	No further checks needed	Final result: True

💡 Found leaf node with remaining sum equal to node value, path sum exists.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
Current Node	root(5)	4	11	7	2	-	-
Remaining Sum	22	17	13	2	2	-	-
Path Found	false	false	false	false	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. As shown in step 4 and 5, we only compare sum when at a leaf node (no children).

What happens if the tree is empty (root is nil)?

The function returns false immediately (step 1), since no path exists in an empty tree.

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

Because we want to check if the remaining sum matches the path ahead. This is shown in the 'Remaining Sum' column updating each step.

Visual Quiz - 3 Questions

Look at the execution table, what is the remaining sum when the node with value 11 is visited?

A 13

B 17

C 2

D 22

💡 Hint

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

At which step does the function find a matching path sum?

A Step 4

B Step 5

C Step 3

D Step 2

💡 Hint

Look for the step where 'sum==val? Yes' appears in the 'Action' column.

If the target sum was 26 instead of 22, what would happen at Step 5?

A sum==val would be true

B sum==val would be false

C The node would not be a leaf

D The function would return false immediately

💡 Hint

Compare the remaining sum and node value at Step 5 in the execution table.

Concept Snapshot

Path Sum Root to Leaf in Binary Tree:
- Start at root, check if leaf node
- If leaf, compare remaining sum with node value
- If match, return true
- Else, recursively check left and right children with sum - node.Val
- Return true if any path matches, else false

Full Transcript

This concept checks if there is a path from the root to any leaf in a binary tree where the sum of node values equals a target sum. The process starts at the root node and checks if it is a leaf. If it is, it compares the remaining sum with the node's value. If they match, the path exists and returns true. If not a leaf, it recursively checks the left and right children, subtracting the current node's value from the sum. The execution table shows each step, the current node, remaining sum, and actions taken. Key moments clarify why leaf checks are important, what happens with an empty tree, and why the sum is updated. The visual quiz tests understanding of these steps. The snapshot summarizes the approach in simple steps.