Path Sum Root to Leaf in Binary Tree in DSA Java

Mental Model

We want to check if there is a path from the top of the tree to any bottom leaf where the numbers add up to a target sum.

Analogy: Imagine walking from the entrance of a maze to any exit, adding numbers on the path. We want to know if any exit path adds up to a magic number.

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

Dry Run Walkthrough

Input: Tree: 5->4->11->7 (left leaf), target sum = 22

Goal: Find if any root-to-leaf path sums to 22

Step 1: Start at root node 5, current sum needed is 22

5 (need 22)

Why: We begin checking from the top with full target sum

Step 2: Go left to node 4, subtract 5 from sum, now need 17

5 -> 4 (need 17)

Why: We move down left path, reducing sum by current node's value

Step 3: Go left to node 11, subtract 4 from sum, now need 13

5 -> 4 -> 11 (need 13)

Why: Continue down left path, updating remaining sum

Step 4: Go left to node 7, subtract 11 from sum, now need 2

5 -> 4 -> 11 -> 7 (need 2)

Why: At leaf node, check if remaining sum equals node value

Step 5: 7 equals needed sum 2? No, backtrack

Back to 11 node

Why: Leaf node value does not match remaining sum, try other paths

Step 6: Go right to node 2 from 11, subtract 11 from sum, now need 2

5 -> 4 -> 11 -> 2 (need 2)

Why: Check other leaf on this branch

Step 7: 2 equals needed sum 2? Yes, path found

5 -> 4 -> 11 -> 2 (need 2)

Why: Leaf node value matches remaining sum, success

Result:

5 -> 4 -> 11 -> 2 -> null, path sum 22 found: true

Annotated Code

DSA Java

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

public class PathSum {
    public static boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false; // no node means no path
        if (root.left == null && root.right == null) {
            return root.val == targetSum; // leaf check
        }
        // check left and right subtrees with reduced sum
        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);

        int targetSum = 22;
        boolean result = hasPathSum(root, targetSum);
        System.out.println(result);
    }
}

if (root == null) return false; // no node means no path

handle empty subtree as no valid path

if (root.left == null && root.right == null) { return root.val == targetSum; }

check if leaf node value matches remaining sum

return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);

recursively check left and right subtrees with updated sum

Output

true

Complexity Analysis

Time: O(n) because we visit each node once to check paths

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Compared to iterative BFS, recursion is simpler but uses call stack; BFS uses queue and may use more memory in wide trees

Edge Cases

Empty tree

Returns false because no path exists

DSA Java

if (root == null) return false; // no node means no path

Single node tree where node value equals target sum

Returns true because root is leaf and matches sum

DSA Java

if (root.left == null && root.right == null) { return root.val == targetSum; }

Single node tree where node value does not equal target sum

Returns false because no matching path

DSA Java

if (root.left == null && root.right == null) { return root.val == targetSum; }

When to Use This Pattern

When asked if a root-to-leaf path sums to a target, use recursive depth-first search subtracting node values from the target.

Common Mistakes

Mistake: Checking sum at non-leaf nodes instead of only at leaves
Fix: Only compare remaining sum to node value when at leaf nodes (no children)

Mistake: Not subtracting current node's value from target sum before recursive calls
Fix: Pass targetSum - root.val to recursive calls to update remaining sum

Summary

Checks if any root-to-leaf path in a binary tree sums to a target value.

Use when you need to verify if a path with a specific sum exists from top to bottom of a tree.

The key is to subtract node values from the target sum as you go down and check only at leaves.

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