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 False if no path found

Start from the root, check if current node is a leaf and if the path sum equals target. If not leaf, recursively check left and right children.

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 there is a root-to-leaf path with sum equal to targetSum.

Execution Table

Step	Operation	Current Node	Remaining Sum	Action	Visual State
1	Start at root	5	22	Check leaf? No, go left	5 / \ 4 8
2	Go left child	4	17	Check leaf? No, go left	5 / \ 4 8 / / \ 11 13 4
3	Go left child	11	13	Check leaf? No, go left	5 / \ 4 8 / / \ 11 13 4 / \ 7 2
4	Go left child	7	6	Check leaf? Yes, sum==target? No	Same as above
5	Backtrack, go right child	2	6	Check leaf? Yes, sum==target? No	Same as above
6	Backtrack to 4, go right child	null	17	No node, return false	Same as above
7	Backtrack to 5, go right child	8	17	Check leaf? No, go left	5 / \ 4 8 / / \ 11 13 4
8	Go left child	13	9	Check leaf? Yes, sum==target? No	Same as above
9	Backtrack, go right child	4	9	Check leaf? No, go left	Same as above / \ 1 null
10	Go left child	1	5	Check leaf? Yes, sum==target? Yes	Leaf found with correct sum
11	Return True	1	5	Path found	Path: 5 -> 4 -> 8 -> 4 -> 1
12	End	null	null	Stop search	Final path sum found

💡 Found leaf node with path sum equal to targetSum, so returns True

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10	Final
Current Node	5	5	4	11	7	2	4 (null)	8	13	4	1	1
Remaining Sum	22	22	17	13	6	6	17	17	9	9	5	5
Return Value	N/A	N/A	N/A	N/A	False	False	False	N/A	False	N/A	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. The check at step 4 and 5 ensures we only compare sums when at a leaf node, as shown in execution_table rows 4 and 5.

What happens when a child node is null?

The function returns false immediately (step 6), meaning no path through that branch. This prevents errors and stops unnecessary recursion.

How does the remaining sum change during recursion?

At each step, the current node's value is subtracted from the remaining sum before going deeper, as seen in the 'Remaining Sum' column in variable_tracker.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the remaining sum when at node 11?

A 17

B 22

C 13

D 5

💡 Hint

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

At which step does the function find a leaf node with the correct path sum?

A Step 10

B Step 4

C Step 8

D Step 2

💡 Hint

Look for 'Check leaf? Yes, sum==target? Yes' in the Action column of execution_table.

If the left child of node 4 was null, what would happen at step 2?

A The function would return true immediately

B The function would check the right child instead

C The function would stop and return false

D The function would continue to check the left child

💡 Hint

Refer to step 6 where a null child causes return false and the function tries the other child.

Concept Snapshot

Path Sum Root to Leaf in Binary Tree:
- Start at root, subtract node value from target sum
- If leaf node, check if remaining sum equals node value
- Recursively check left and right children
- Return true if any path matches sum
- Return false if no path found

Full Transcript

This concept checks if a binary tree has a root-to-leaf path where the sum of node values equals a target sum. Starting at the root, we subtract the current node's value from the target sum. If the node is a leaf, we check if the remaining sum equals the node's value. If yes, we return true. Otherwise, we recursively check the left and right children with the updated sum. If no path matches, we return false. The execution table shows step-by-step traversal and sum updates, with backtracking when paths do not match. Key moments clarify why leaf checks and null child handling are important.

Practice

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

easy

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

B. The maximum depth of the binary tree

C. The total number of leaf nodes in the binary tree

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

2. Step 2: Differentiate from other tree properties

   This is different from finding max depth, counting leaves, or summing all nodes. It specifically checks for a path with a certain sum.

3. Final Answer:

   If there exists a root-to-leaf path with a sum equal to a given target -> Option A

4. Quick Check:

   Path sum means root-to-leaf sum check [OK]

Hint: Look for root-to-leaf path sums, not total or max values [OK]

Common Mistakes:

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

2. Which of the following is the correct C function signature to check if a binary tree has a root-to-leaf path with a given sum?

easy

A. int hasPathSum(struct TreeNode* root, int sum);

B. void hasPathSum(struct TreeNode* root, int sum);

C. int hasPathSum(int root, int sum);

D. bool hasPathSum(struct TreeNode* root);

Solution

1. Step 1: Identify correct parameter types

   The function needs the root pointer of the tree (struct TreeNode*) and the target sum (int).

2. Step 2: Identify correct return type

   The function returns an int (usually 0 or 1) indicating false or true for path existence.

3. Final Answer:

   int hasPathSum(struct TreeNode* root, int sum); -> Option A

4. Quick Check:

   Function returns int and takes root pointer and sum [OK]

Hint: Function returns int and takes root pointer plus sum [OK]

Common Mistakes:

• Using void return type instead of int
• Passing root as int instead of pointer
• Missing sum parameter

3. Given the binary tree below and target sum = 22, what will the function hasPathSum return?

    5
   / \
  4   8
 /   / \
11  13  4
/  \      \
7    2      1

medium

A. 0

B. 1

C. Error

D. Undefined

Solution

1. Step 1: Find root-to-leaf paths and their sums

   Paths and sums: - 5->4->11->7 = 27 - 5->4->11->2 = 22 - 5->8->13 = 26 - 5->8->4->1 = 18

2. Step 2: Check if any path sum equals 22

   The path 5->4->11->2 sums to 22, so the function returns true (1).

3. Final Answer:

   1 -> Option B

4. Quick Check:

   Path sum 22 exists = 1 [OK]

Hint: Check all root-to-leaf sums carefully [OK]

Common Mistakes:

• Ignoring leaf node condition
• Stopping at non-leaf nodes
• Miscomputing sums

4. Consider this buggy C code snippet for path sum check:

int hasPathSum(struct TreeNode* root, int sum) {
  if (!root) return 0;
  if (!root->left && !root->right && root->val == sum) return 1;
  return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
}

What is the bug in this code?

medium

A. It misses subtracting root->val from sum

B. It incorrectly returns 1 for non-leaf nodes

C. It does not handle empty tree correctly

D. It correctly implements the path sum check

Solution

1. Step 1: Analyze base cases

   Returns 0 if root is NULL (empty tree). Returns 1 if leaf node value equals sum.

2. Step 2: Analyze recursive calls

   Recursively checks left and right subtrees with updated sum (sum - root->val).

3. Final Answer:

   It correctly implements the path sum check -> Option D

4. Quick Check:

   Code matches standard path sum logic [OK]

Hint: Check base cases and recursive calls carefully [OK]

Common Mistakes:

• Missing leaf node check
• Not subtracting root value from sum
• Returning wrong values for NULL nodes

5. You want to modify the path sum function to return all root-to-leaf paths where the sum equals the target. Which data structure is best to store the current path during recursion?

hard

A. A queue to process nodes level by level

B. A hash map to store node values and counts

C. A stack or dynamic array to track nodes in current path

D. A linked list to store all leaf nodes

Solution

1. Step 1: Understand path tracking during recursion

   To record the current path from root to current node, a stack or dynamic array is used to push and pop nodes as recursion goes deeper or backtracks.

2. Step 2: Differentiate from other data structures

   A queue is for breadth-first traversal, hash map is for counting, linked list for storing nodes but not efficient for backtracking paths.

3. Final Answer:

   A stack or dynamic array to track nodes in current path -> Option C

4. Quick Check:

   Use stack/array for path tracking [OK]

Hint: Use stack or array to track path during recursion [OK]

Common Mistakes:

• Using queue instead of stack for path tracking
• Not backtracking path correctly
• Using hash map for path storage