Binary Tree Path Sum

Example: Let's create a binary tree and check if there exists a path with a given sum.

# Node class definition
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# Create a binary tree
root = Node(5)
root.left = Node(4)
root.right = Node(8)
root.left.left = Node(11)
root.right.left = Node(13)
root.right.right = Node(4)
root.left.left.left = Node(7)
root.left.left.right = Node(2)
root.right.right.right = Node(1)

# Check if there exists a path with sum = 22
def has_path_sum(root, target_sum):
    if root is None:
        return False
    if root.left is None and root.right is None and root.value == target_sum:
        return True
    return (has_path_sum(root.left, target_sum - root.value) or
            has_path_sum(root.right, target_sum - root.value))

has_path = has_path_sum(root, 22)
print(has_path)
# Output: True

In this example, we define a Node class that represents a node in the binary tree. Each node has a value, left child, and right child.

We create a binary tree with the given values.

To check if there exists a path with a given sum, we define a recursive function has_path_sum that takes a node and the target sum as arguments. In this function, we perform the following checks:

• If the current node is None, it means we have reached a null node, so we return False.
• If the current node is a leaf node (both left and right children are None), and its value is equal to the target sum, we have found a path with the desired sum, so we return True.
• We recursively check if there exists a path with the target sum in either the left subtree or the right subtree. To do this, we subtract the value of the current node from the target sum and call has_path_sum on the left and right children.
• If any of the recursive calls return True, it means there exists a path with the target sum, so we return True. Otherwise, we return False.

Finally, we call has_path_sum on the root of the binary tree with the target sum of 22 and store the result in has_path. We print the result.

Let's solve a question using the concept of Binary Tree Path Sum. The question is "Path Sum II," which requires finding all root-to-leaf paths in a binary tree where the sum of all nodes' values is equal to a given target sum.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class Solution:
    def path_sum(self, root, target_sum):
        def find_paths(node, curr_sum, path, result):
            if node is None:
                return
            curr_sum += node.value
            path.append(node.value)
            if node.left is None and node.right is None and curr_sum == target_sum:
                result.append(path[:])
            else:
                find_paths(node.left, curr_sum, path, result)
                find_paths(node.right, curr_sum, path, result)
            path.pop()

        if root is None:
            return []
        result = []
        find_paths(root, 0, [], result)
        return result

# Create an instance of Solution
solution = Solution()

# Create a binary tree
root = Node(5)
root.left = Node(4)
root.right = Node(8)
root.left.left = Node(11)
root.right.left = Node(13)
root.right.right = Node(4)
root.left.left.left = Node(7)
root.left.left.right = Node(2)
root.right.right.left = Node(5)
root.right.right.right = Node(1)

# Find all paths with sum = 22
paths = solution.path_sum(root, 22)
print(paths)
# Output: [[5, 4, 11, 2], [5, 8, 4, 5]]

In this solution, we define a Node class to represent a node in the binary tree. We also define a Solution class that contains the path_sum method to find all root-to-leaf paths in the binary tree with the given target sum.

The path_sum method is implemented using a recursive helper function find_paths. It takes a node, current sum, path, and result as arguments. The function performs the following steps:

• If the current node is None, it means we have reached a null node, so we return.
• We update the current sum by adding the value of the current node and append the node's value to the path.
• If the current node is a leaf node and the current sum is equal to the target sum, we have found a valid path. We append a copy of the path to the result list.
• If the current node is not a leaf node or the current sum is not equal to the target sum, we recursively call find_paths on the left and right children, passing the updated current sum and path.
• After the recursive calls, we remove the last element from the path to backtrack.

In the path_sum method, we handle the case when the root is None by returning an empty list. We create an empty result list to store the valid paths. We call the find_paths helper function on the root node with the initial current sum of 0, an empty path, and the result list. Finally, we return the result list containing all the root-to-leaf paths with the target sum.

The time complexity of the solution is O(n), where n is the number of nodes in the binary tree, as we visit each node once. The space complexity is O(n), where n is the number of valid paths in the binary tree. This is because we store each valid path in the result list, and in the worst case, all nodes could be part of a valid path, resulting in O(n) space usage.