112. Path Sum 🔗

Difficulty: Easy - Tags: Binary Tree, Depth-First Search (DFS), Recursion

LeetCode Problem Link

---

Problem Statement 📜

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that the sum of all the node values along the path equals targetSum.

• A leaf is a node with no children.

---

Examples 🌟

🔹 Example 1:

Input:

root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22

Output:

true

Explanation:

The root-to-leaf path [5,4,11,2] has a sum of 22.

---

🔹 Example 2:

Input:

root = [1,2,3], targetSum = 5

Output:

false

Explanation:

There are two root-to-leaf paths:

• Path 1 -> 2: Sum is 3.

• Path 1 -> 3: Sum is 4.

Neither equals 5.

---

🔹 Example 3:

Input:

root = [], targetSum = 0

Output:

false

Explanation:

The tree is empty, so there are no root-to-leaf paths.

---

Constraints ⚙️

• The number of nodes in the tree is in the range [0, 5000].

• -1000 <= Node.val <= 1000

• -1000 <= targetSum <= 1000

---

Solution 💡

To determine if there is a root-to-leaf path with the given targetSum:

1. Use Depth-First Search (DFS) to traverse the binary tree.

2. Subtract the current node's value from targetSum as you traverse.

3. Check if:

   • The current node is a leaf.

   • The updated targetSum equals 0.

---

Java Solution

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        // Base case: if the tree is empty, there is no path
        if (root == null) return false;

        // If it's a leaf node, check if the targetSum matches the node's value
        if (root.left == null && root.right == null) {
            return targetSum == root.val;
        }

        // Recursively check left and right subtrees
        int remainingSum = targetSum - root.val;
        return hasPathSum(root.left, remainingSum) || hasPathSum(root.right, remainingSum);
    }
}

---

Explanation of the Solution

1. Base Case:

   • If the root is null, the tree is empty, and no path exists.

2. Leaf Node Check:

   • If the node has no children, compare its value to the remaining targetSum.

3. Recursive Calls:

   • Subtract the current node's value from targetSum.

   • Recursively check the left and right subtrees.

4. Combine Results:

   • Use the logical OR operator to combine results from both subtrees.

---

Time Complexity ⏳

• O(n): Each node is visited once.

Space Complexity 💾

• O(h): Where h is the height of the tree (due to recursion stack).

---

Follow-up Challenges 🧐

• How would you modify this solution to return all paths with the target sum?

• Can you solve this iteratively instead of using recursion?

You can find the full solution here.