Path Sum Root to Leaf in Binary Tree in DSA Java - 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 Java

boolean hasPathSum(TreeNode node, int sum) {
  if (node == null) return false;
  if (node.left == null && node.right == null) 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 State
1	Start at root	5	22	?	5 / \ 4 8 / / \ 11 13 4 / \ 7 2 1
2	Check leaf?	5	22	No	Same as above
3	Recurse left	4	17	?	4 / 11 / 7 2
4	Check leaf?	4	17	No	Same as above
5	Recurse left	11	13	?	11 / 7 2
6	Check leaf?	11	13	No	Same as above
7	Recurse left	7	2	?	7
8	Check leaf?	7	2	Yes	7
9	Leaf node sum check	7	2	False	7
10	Recurse right	2	2	?	2
11	Check leaf?	2	2	Yes	2
12	Leaf node sum check	2	2	True	2
13	Return true up	11	13	True	11 subtree
14	Return true up	4	17	True	4 subtree
15	Return true up	5	22	True	Whole tree

💡 Returned true at leaf node with value 2 where remaining sum matched.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	After Step 10	Final
Current Node	5	4	11	7	2	null
Sum Remaining	22	17	13	2	2	N/A
Return Value	?	?	?	False	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 steps 2, 6, 8, 11 where leaf check happens before sum comparison.

Why do we subtract node value from sum when recursing?

We track remaining sum needed. At each step, sum reduces by current node's value (see 'Sum Remaining' column).

What happens if a subtree returns true?

The function returns true immediately up the call stack (steps 12-15), no need to check other paths.

Visual Quiz - 3 Questions

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

A 13

B 17

C 2

D 22

💡 Hint

Check the 'Sum Remaining' column at step 5.

At which step does the function first return true?

A Step 9

B Step 12

C Step 15

D Step 7

💡 Hint

Look at the 'Return Value' column for the first 'True' value.

If the leaf node with value 2 was changed to 3, what would happen at step 12?

A Return true

B Return false

C Return null

D Error

💡 Hint

Sum remaining at step 12 is 2, leaf value changed to 3, so sum == node.val check fails.

Concept Snapshot

Path Sum Root to Leaf in Binary Tree:
- Start at root, check if node is leaf
- If leaf, compare sum with node value
- Else recurse left and right with sum - node.val
- Return true if any path matches sum
- Returns false if no path matches

Full Transcript

This concept checks if there is a root-to-leaf path in a binary tree where the sum of node values equals a target sum. Starting at the root, we check if the node is null, returning false if so. If the node is a leaf, we compare the remaining sum with the node's value. If they match, we return true. Otherwise, we recursively check the left and right subtrees with the updated sum (original sum minus current node's value). The function returns true if any path matches the sum, or false if none do. The execution table traces each step, showing the current node, remaining sum, and return values. Key moments clarify why leaf checks happen first, why sum is updated, and how true returns propagate 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. 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 tree

D. The sum of all node values in the tree

Solution

1. Step 1: Understand the problem statement

   The problem asks if any path from the root node down to any leaf node sums exactly to a given target value.

2. Step 2: Identify what is being checked

   We check if such a path exists, not the maximum depth or total sum of all nodes.

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 check = existence of target sum path [OK]

Hint: Focus on root-to-leaf paths and their sums [OK]

Common Mistakes:

• Confusing total tree sum with path sum
• Checking any path, not root-to-leaf
• Looking for maximum depth instead

2. Which of the following Java method signatures correctly represents a function to check path sum in a binary tree node class?

easy

A. public void hasPathSum(TreeNode root, int targetSum)

B. public int hasPathSum(TreeNode root, int targetSum)

C. public String hasPathSum(TreeNode root, int targetSum)

D. public boolean hasPathSum(TreeNode root, int targetSum)

Solution

1. Step 1: Identify the return type for path sum check

   The function should return true or false, so the return type must be boolean.

2. Step 2: Check method signature correctness

   public boolean hasPathSum(TreeNode root, int targetSum) returns boolean and takes root node and target sum as parameters, matching the problem requirements.

3. Final Answer:

   public boolean hasPathSum(TreeNode root, int targetSum) -> Option D

4. Quick Check:

   Return type boolean for true/false check [OK]

Hint: Return boolean for yes/no path sum check [OK]

Common Mistakes:

• Using int or void return type instead of boolean
• Returning String instead of boolean
• Incorrect parameter types

3. What will be the output of the following code snippet?

class TreeNode {
  int val;
  TreeNode left, right;
  TreeNode(int val) { this.val = val; }
}

public class Solution {
  public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) return false;
    if (root.left == null && root.right == null) return root.val == targetSum;
    return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
  }

  public static void main(String[] args) {
    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);

    Solution sol = new Solution();
    System.out.println(sol.hasPathSum(root, 22));
  }
}

medium

A. true

B. false

C. Compilation error

D. Runtime exception

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: Evaluate the recursive calls

   The function returns true because the path sum 22 exists, so it prints true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Path 5+4+11+2 = 22 exists [OK]

Hint: Look for any root-to-leaf path matching target sum [OK]

Common Mistakes:

• Ignoring leaf node condition
• Subtracting sum incorrectly
• Assuming sum must be from root to any node

4. Identify the bug in the following code for checking path sum and select the correct fix:

public boolean hasPathSum(TreeNode root, int targetSum) {
  if (root == null) return false;
  if (root.left == null && root.right == null) return root.val == targetSum;
  return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum);
}

medium

A. Change return type to int

B. Subtract root.val from targetSum in recursive calls

C. Check only left subtree for path sum

D. Return true if root is null

Solution

1. Step 1: Analyze recursive call parameters

   The code calls hasPathSum with the same targetSum without subtracting root.val, so it doesn't reduce the sum along the path.

2. Step 2: Correct the recursive calls

   Subtract root.val from targetSum in recursive calls to track remaining sum needed.

3. Final Answer:

   Subtract root.val from targetSum in recursive calls -> Option B

4. Quick Check:

   Update targetSum by subtracting node value [OK]

Hint: Always reduce targetSum by current node's value [OK]

Common Mistakes:

• Not subtracting node value in recursion
• Returning true on null node
• Ignoring right subtree

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?

hard

A. Check for path sums only in positive-valued nodes

B. Use a global variable to track sums instead of recursion

C. No modification needed; standard path sum check works for all values

D. Modify the function to handle negative sums by not stopping at leaf nodes

Solution

1. Step 1: Understand impact of negative values on path sum

   Negative values do not affect the logic; the sum is still accumulated along the path.

2. Step 2: Confirm standard recursive approach works

   The standard recursive subtraction and leaf check works regardless of node values being negative, zero, or positive.

3. Final Answer:

   No modification needed; standard path sum check works for all values -> Option C

4. Quick Check:

   Standard method handles all integer values [OK]

Hint: Standard recursion handles negative values fine [OK]

Common Mistakes:

• Thinking negative values break the logic
• Trying to skip negative nodes
• Changing leaf node condition unnecessarily