Path Sum Leetcode Problem 112 [Python Solution]

The Path Sum LeetCode problem is categorized as “Easy” and falls under the domain of trees; a classic example of a tree traversal problem.

Before we dive into the solution, let’s understand the problem statement.

Problem Overview

Question: Given the root of a binary tree and an integer targetSum, our task is to determine whether there exists a root-to-leaf path where the sum of values along the path equals targetSum.

In other words, we need to find a path from the root to a leaf node in the binary tree, where the sum of the node values in the path is equal to the given targetSum.

A leaf node is a node with no children.

Let’s illustrate this problem with some 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 with the target sum is shown below:

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

The path is [5, 4, 11, 2], and the sum of these values equals 22.

Example 2:

Input:

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

Output: false

Explanation:
In this case, there are two root-to-leaf paths in the tree:

1. The path [1, 2], with a sum of 3.
2. The path [1, 3], with a sum of 4.

There is no path with a sum equal to 5.

Example 3:

Input:

root = []
targetSum = 0

Output: false

Explanation:
Since the tree is empty, there are no root-to-leaf paths.

Constraints:

• The number of nodes in the tree is in the range [0, 5000].
• The values of the tree nodes (Node.val) are in the range [-1000, 1000].
• The targetSum is in the range [-1000, 1000].

Now that we understand the problem, let’s explore potential approaches to solve it and then implement an efficient Python solution.

Understanding Path Sum Constraints

Before we delve into the solution, it’s essential to understand the constraints of the Path Sum problem.

These constraints help us shape our approach and optimize the solution.

1. The problem involves a binary tree, not necessarily a binary search tree.

This means there is no specific order to the nodes, and we must explore all possible paths.

2. A leaf node is defined as a node with no children, meaning it doesn’t have a left or right child.
3. We need to find a path from the root to a leaf node in the binary tree, such that the sum of node values along the path equals the given targetSum.

To achieve this, we can perform a Depth-First Search (DFS) traversal of the tree, maintaining a running total of the node values encountered along the path.

We’ll return True if we find a leaf node with a sum equal to the targetSum.

Path Sum LeetCode Problem Solution

1. Bruteforce Approach

A straightforward approach to solving the Path Sum problem is to perform a depth-first traversal of the tree.

Starting from the root, we’ll explore all possible paths to leaf nodes and check if the sum along each path equals the targetSum.

If we find a path that meets this condition, we return True.

Otherwise, we continue the search.

Here’s a Python code implementation of this brute-force approach:

def hasPathSum(self, root, targetSum):
    if not root:
        return False

    def dfs(node, current_sum):
        # Update the current sum by adding the value of the current node.

current_sum += node.val

        # Check if the current node is a leaf node and the sum matches the target.

if not node.left and not node.right and current_sum == targetSum:
            return True

        # Recursively explore the left and right subtrees.

left_result = dfs(node.left, current_sum)
        right_result = dfs(node.right, current_sum)

        # Return True if either the left or right subtree has a valid path.

return left_result or right_result

    return dfs(root, 0)

In this code:

• We start by checking if the root is None.

If the tree is empty, there is no path, and we return False.

• The dfs function is a recursive function that performs depth-first traversal.

It takes two parameters: node (the current node) and current_sum (the sum of values along the current path).

• Inside the dfs function, we add the value of the current node to current_sum.
• We check if the current node is a leaf node (no left or right child) and if the current_sum matches the targetSum.

If both conditions are met, we return True, indicating that a valid path has been found.

• We then recursively call the dfs function for the left and right subtrees, storing the results in left_result and right_result.
• We return True if either the left or right subtree has a valid path (i.e., if left_result or right_result is True).

This brute-force approach works, but it may not be the most efficient solution.

It involves exploring all possible paths in the tree, resulting in a time complexity of O(n), where n is the number of nodes in the tree.

Additionally, the space complexity is O(h), where h is the height of the tree (in the worst case, h can be n for an unbalanced tree).

Now, let’s explore a more efficient approach that optimizes the time complexity.

2. An Efficient Approach with Iterative DFS

While the brute-force approach is correct, it can be optimized to achieve better time and space complexity.

In the previous solution, we used a recursive DFS approach.

Now, we’ll implement an iterative DFS approach using a stack data structure.

Here’s the Python code for the efficient approach:

def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False

        # Create a stack to store tuples of nodes and their corresponding remaining sums.
        stack = [(root, targetSum - root.val)]

        while stack:
            node, current_sum = stack.pop()

            # If we reach a leaf node and the sum equals the targetSum, return True.
            if not node.left and not node.right and current_sum == 0:
                return True

            # Explore the right subtree if it exists and update the remaining sum.
            if node.right:
                stack.append((node.right, current_sum

    - node.right.val))

            # Explore the left subtree if it exists and update the remaining sum.
            if node.left:
                stack.append((node.left, current_sum - node.left.val))

        # If no valid path is found, return False.
        return False

In this code:

• We start by checking if the root is None.

If the tree is empty, we return False.

• We use a stack to perform an iterative depth-first traversal.

Each element in the stack is a tuple containing a node and the remaining sum required to reach the targetSum.

• Inside the while loop, we pop the top element from the stack, representing the current node and its remaining sum.
• We check if the current node is a leaf node (no left or right child) and if the current_sum equals 0.

If both conditions are met, we return True.

• If the current node has a right child, we update the remaining sum and push the right child and its remaining sum onto the stack.
• Similarly, if the current node has a left child, we update the remaining sum and push the left child and its remaining sum onto the stack.
• The loop continues until we either find a valid path and return True or exhaust all possible paths and return False.

This efficient approach achieves the same result as the brute-force approach but in a more optimized way.

It eliminates the need for recursive calls and, in most cases, reduces the space complexity to O(h), where h is the height of the tree.

Now that we have an efficient Python solution, let’s discuss the time and space complexity.

Time and Space Complexity

In our efficient Python solution, we use an iterative depth-first traversal to explore the binary tree.

Here are the time and space complexities:

Time Complexity: The time complexity of our solution is O(n), where n is the number of nodes in the tree.

This is because, in the worst case, we need to visit every node in the tree once to determine whether a valid path exists.

Space Complexity: The space complexity depends on the height of the tree, denoted as h.

In the best case, when the tree is balanced, the space complexity is O(log n), where log n is the height of the tree.

However, in the worst case, if the tree is completely unbalanced (essentially a linked list), the space complexity is O(n) since we need to store all nodes in the stack.

Therefore, the space complexity can be O(log n) to O(n).

Reasoning Behind Our Efficient Approach

The key to our efficient approach is leveraging an iterative depth-first traversal with a stack to explore the binary tree.

This approach eliminates the need for recursive function calls and optimizes space usage.

Here’s a step-by-step breakdown of how our approach works:

1. We start at the root of the tree and initialize a stack to store tuples of nodes and their remaining sums.
2. We push the root node onto the stack along with the remaining sum required to reach the targetSum (targetSum – root.val).
3. We enter a while loop that continues until the stack is empty.
4. Inside the loop, we pop the top element from the stack, representing the current node and its remaining sum.
5. We check if the current node is a leaf node (no left or right child) and if the current_sum equals 0.

If both conditions are met, we return True since we have found a valid path.

6. If the current node has a right child, we update the remaining sum (subtract the value of the right child) and push the right child and its updated remaining sum onto the stack.
7. Similarly, if the current node has a left child, we update the remaining sum (subtract the value of the left child) and push the left child and its updated remaining sum onto the stack.
8. The loop continues until we either find a valid path and return True or exhaust all possible paths and return False.

The efficient approach avoids unnecessary recursive calls, which can lead to stack overflow errors for deep trees.

Instead, it utilizes an iterative approach, making it more memory-efficient and better suited to handle large trees.

Related Interview Questions By Company:

• Is Subsequence LeetCode
• Roman To Integer LeetCode
• Maximum Number Of Balloons LeetCode

Related Interview Questions By Difficulty:

• Binary Tree Inorder Traversal LeetCode
• Trim A Binary Search Tree LeetCode
• Binary Tree Postorder Traversal LeetCode

Related Interview Questions By Category:

• IPO LeetCode
• Reverse String LeetCode
• Binary Tree Preorder Traversal LeetCode

Conclusion

In this blog post, we tackled the Path Sum problem from LeetCode.

We discussed the problem statement, explored two different approaches, and implemented an efficient Python solution using an iterative depth-first traversal with a stack.

To recap, we first discussed the problem’s constraints, which helped us shape our approach.

We then implemented a brute-force approach that involved recursive depth-first traversal.

While correct, it had a time complexity of O(n) and a space complexity of O(h).

Next, we introduced our more efficient approach, which used an iterative depth-first traversal with a stack.

This approach achieved the same result but with improved space complexity, ranging from O(log n) to O(n), depending on the tree’s height.

In the end, we hope this blog post helps you understand how to solve the Path Sum problem efficiently.

If you have any questions, suggestions, or comments, please feel free to share them.

We encourage you to try the problem on LeetCode, test the code, and explore further.

Happy coding!

If you found this content helpful, please like and engage to support our our platform.

For additional support, consider checking out our Patreon.

We appreciate your support and look forward to seeing you in the next coding session.

LeetCode Problem Link

Now, it’s your turn to give it a try and explore the world of binary tree traversal.

Feel free to comment, ask questions, make suggestions, and share this content with fellow coding enthusiasts.

Happy coding!