112. Path Sum
Model: qwen2.5-coder:14b
Topics: Tree,Depth-first Search
FAANG asked: 1
Acceptance rate: 42.6%
Problem Breakdown
The problem asks us to determine if there exists a path from the root node to any leaf node in a binary tree such that the sum of all node values along this path equals a given target sum. The inputs are the root of the binary tree and an integer representing the target sum. The output is a boolean value: true if such a path exists, and false otherwise.
Inputs:
root: The root node of the binary tree.targetSum: An integer representing the desired sum of values along a path from the root to a leaf.
Outputs:
- A boolean indicating whether a valid path exists.
Implicit Constraints/Edge Cases:
- If the tree is empty (
rootisnull), returnfalse. - The target sum can be negative, zero, or positive.
- Node values can range from
-1000to1000.
Intuition
A brute-force approach would involve generating all possible paths from the root to leaf nodes and checking if any of these paths sum up to the target. This approach is inefficient because it requires traversing every node multiple times, leading to a time complexity of O(n^2) in the worst case.
The key insight is to use Depth-First Search (DFS) to traverse the tree while keeping track of the remaining sum needed to reach the target. By doing this, we can efficiently determine if a valid path exists without generating all possible paths explicitly.
Approach
- Base Case: If the current node is
null, returnfalsebecause there’s no path through a non-existent node. - Leaf Node Check: If the current node is a leaf (i.e., it has no left or right children), check if its value equals the remaining target sum. If it does, return
true; otherwise, returnfalse. - Recursive Case: For non-leaf nodes, recursively check both the left and right subtrees with the updated target sum (
targetSum - current_node.val). If either subtree returnstrue, then a valid path exists through that subtree.
Complexity Analysis
Time Complexity: O(n), where n is the number of nodes in the tree. Each node is visited once. Space Complexity: O(h), where h is the height of the tree. This accounts for the recursion stack space. In the worst case (a skewed tree), this could be O(n).
Solution
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def hasPathSum(root: TreeNode, targetSum: int) -> bool:
# Base case: if the current node is None, return False
if not root:
return False
# Check if we are at a leaf node and its value equals the remaining target sum
if not root.left and not root.right:
return root.val == targetSum
# Recursively check left and right subtrees with updated target sum
return hasPathSum(root.left, targetSum - root.val) or hasPathSum(root.right, targetSum - root.val)
Edge Cases Handled
- Empty Tree: If the input tree is empty (
rootisnull), the function returnsfalseimmediately. - Negative Target Sum: The function correctly handles negative target sums by subtracting node values and checking if a leaf node matches the remaining sum.
- Single Node Tree: If the tree consists of only one node, the function checks if that node’s value equals the target sum.
- No Valid Path: If no path from root to any leaf sums up to the target, the function returns
false.
The provided solution is correct, efficient, and clear. It handles all edge cases as described in the problem statement. The time complexity is O(n), which is optimal for this type of tree traversal problem, and the space complexity is O(h), where h is the height of the tree.