To solve the “Binary Tree Path Sum” problem, we can use a recursive approach to traverse the tree and check if there is a root-to-leaf path with the given sum.

Here’s the implementation:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def has_path_sum(root: TreeNode, target_sum: int) -> bool:
    if not root:
        return False

    # Check if the current node is a leaf
    if not root.left and not root.right:
        return root.val == target_sum

    # Recursively check for the sum on the left and right subtrees
    left_has_path_sum = has_path_sum(root.left, target_sum - root.val)
    right_has_path_sum = has_path_sum(root.right, target_sum - root.val)

    # Return True if either subtree has a path with the given sum
    return left_has_path_sum or right_has_path_sum

# Example usage:
tree = TreeNode(5,
                TreeNode(4, 
                	     TreeNode(11, 
                	     	      TreeNode(7), 
                	     	      TreeNode(2)
                	     	      )
                	     ),
                TreeNode(8, 
                	     TreeNode(13), 
                	     TreeNode(4, 
                	     	      None, 
                	     	      TreeNode(1)
                	     	      )
                	     )
                )

result_true = has_path_sum(tree, 22)  
print(result_true)
assert result_true is True

result_false = has_path_sum(tree, 28)  
print(result_false)
assert result_false is False

Explanation:

  • The has_path_sum function recursively checks for a path with the given sum in the binary tree.
  • If the current node is a leaf (no left or right child), it checks if the current node’s value equals the remaining sum.
  • If the current node is not a leaf, it recursively checks for the sum on the left and right subtrees.
  • The function returns True if either subtree has a path with the given sum.

Time Complexity:

The time complexity is O(N), where N is the number of nodes in the binary tree. We visit each node once during the traversal.

Space Complexity:

The space complexity is O(H), where H is the height of the binary tree. This is the maximum depth of the recursive call stack. In the worst case, the depth of the recursion is equal to the height of the tree.