Path Sum Root to Leaf in Binary Tree in DSA Java - Build from Scratch

Path Sum Root to Leaf in Binary Tree

📖 Scenario: Imagine you have a simple family tree where each person has a number representing their age. You want to check if there is a path from the oldest ancestor (root) down to a youngest family member (leaf) where the sum of ages equals a specific number.

🎯 Goal: Build a Java program that creates a binary tree with exact ages, sets a target sum, and checks if any root-to-leaf path adds up to that sum.

📋 What You'll Learn

Create a binary tree with the exact node values given

Create a variable called targetSum with the exact value given

Write a method hasPathSum that checks if any root-to-leaf path sums to targetSum

Print the result as true or false

💡 Why This Matters

🌍 Real World

Checking path sums in trees is useful in decision-making systems, where each node represents a choice with a cost or value, and you want to find a path meeting a budget or target.

💼 Career

Understanding tree traversal and recursion is fundamental for software engineers, especially in roles involving data structures, algorithms, and coding interviews.

1

Create the Binary Tree

Create a binary tree with the exact structure and node values: root node with value 5, left child with value 4, right child with value 8, left child of left child with value 11, left and right children of node 11 with values 7 and 2 respectively, left child of right child with value 13, right child of right child with value 4, and right child of node 4 (right child of 8) with value 1. Use the class TreeNode with int val, TreeNode left, and TreeNode right.

DSA Java

public class Main {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val) { this.val = val; }
    }

    public static void main(String[] args) {
        // Create the binary tree nodes and link them
        // Your code here
    }
}

Hint

Start by creating the root node with value 5. Then add left and right children as described. Continue linking children to build the exact tree structure.

2

Set the Target Sum

Create an integer variable called targetSum and set it to 22 inside the main method, after creating the tree.

DSA Java

public class Main {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val) { this.val = 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);
        // Create the targetSum variable and set it to 22
        // Your code here
    }
}

Hint

After building the tree, create a variable named targetSum and assign it the value 22.

3

Write the hasPathSum Method

Write a static method called hasPathSum that takes a TreeNode root and an int sum as parameters. It should return true if there is a root-to-leaf path in the tree where the sum of node values equals sum. Otherwise, return false. Use recursion and check if the current node is null, if it is a leaf, and subtract the node's value from sum when recurring.

DSA Java

public class Main {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val) { this.val = val; }
    }

    public static boolean hasPathSum(TreeNode root, int sum) {
        // Implement the recursive check for path sum
        // Your code here
    }

    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;
    }
}

Hint

Check if the current node is null and return false. If it is a leaf node, check if the remaining sum equals the node's value. Otherwise, recursively check left and right children with the updated sum.

4

Print the Result

In the main method, after setting targetSum, call hasPathSum(root, targetSum) and print the result using System.out.println.

DSA Java

public class Main {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val) { this.val = val; }
    }

    public static boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            return sum == root.val;
        }
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - 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;
        // Print the result of hasPathSum
        // Your code here
    }
}

Hint

Call hasPathSum(root, targetSum) and print the result using System.out.println.

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