Domain 1EasyCORE

Path Sum

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.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Tree#Depth-first Search

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 (root is null), return false.
  • The target sum can be negative, zero, or positive.
  • Node values can range from -1000 to 1000.

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

  1. Base Case: If the current node is null, return false because there’s no path through a non-existent node.
  2. 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, return false.
  3. 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 returns true, 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 (root is null), the function returns false immediately.
  • 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.