path_sum.py

from pathlib import Path
import sys

sys.path.append(str(Path(__file__).resolve().parent.parent))

from binary_tree import create_binary_tree


class Solution:
    def pathSum(self, root, target):
        if root is None:
            return False

        if not root.left and not root.right:
            return root.val == target

        target -= root.val

        left = self.pathSum(root.left, target)
        right = self.pathSum(root.right, target)

        return left or right

    def hasPathSum(self, root, targetSum):
        if not root:
            return False

        stack = [(root, root.val)]

        while stack:
            node, curr_sum = stack.pop()

            if not node.left and not node.right and curr_sum == targetSum:
                return True

            if node.right:
                stack.append((node.right, curr_sum + node.right.val))

            if node.left:
                stack.append((node.left, curr_sum + node.left.val))

        return False

        # Time Complexity: O(n)
        # Space Complexity: O(h)


if __name__ == "__main__":

    root = [4, 2, 7, 1, 3, 6, 9]
    bt = create_binary_tree(root)

    solution = Solution()

    target = 17
    result = solution.pathSum(bt, target)
    assert result == True
    print(result)
    print("Test Case 1 Passed!")