Binary Tree Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Function Signature:

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, sum: int) -> bool:
    """
    Check if there is a root-to-leaf path in the binary tree with the given sum.

    Parameters:
    - root: The root of the binary tree.
    - sum: The target sum.

    Returns:
    - bool: True if there is a path with the given sum, False otherwise.
    """
    # Your code here

Example:

# Example Binary Tree:
#        5
#       / \
#      4   8
#     /   / \
#    11  13  4
#   /  \      \
#  7    2      1

tree = TreeNode(5,
                TreeNode(4, 
                	     TreeNode(11, 
                	     	      TreeNode(7), 
                	     	      TreeNode(2)
                	     	      )
                	     ),
                TreeNode(8, 
                	     TreeNode(13), 
                	     TreeNode(4, 
                	     	      None, 
                	     	      TreeNode(1)
                	     	      )
                	     )
                )

# The possible sums are: 
#   5->4->11->7 = 27
#   5->4->11->2 = 22
#   5->8->13 = 26
#   5->8->4->1 = 18

result_true = has_path_sum(tree, 22)  
print(result_true)
assert result_true is True
# Explanation: 5->4->11->2

result_false = has_path_sum(tree, 28)  
print(result_false)
assert result_false is False
# Explanation: No path with sum 28

Note:

• The given binary tree is not necessarily a binary search tree.
• All node values are unique.

Instructions:

• Write the has_path_sum function to solve the problem.
• Implement your solution in Python.
• Provide clear comments in your code.
• Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊