Solution 1 - Recursive DFS

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum. A leaf is a node with no children. We recursively subtract the current node's value from targetSum and check if we reach a leaf with a remaining sum of zero.

TimeComplexity: O(n)

SpaceComplexity: O(h)

""" 0112.1 - Path Sum - Solution 1 - Recursive DFS """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional

#####################################################################################
# Classes
#####################################################################################
class TreeNode:
    """TreeNode Class"""

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


class Solution:
    """Solution Class"""

    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        """Path Sum Function"""
        if not root:
            return False

        targetSum -= root.val

        # Check if current node is a leaf
        if not root.left and not root.right:
            return targetSum == 0

        return self.hasPathSum(root.left, targetSum) or self.hasPathSum(root.right, targetSum)


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    # Example 1: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
    root = TreeNode(5)
    root.left = TreeNode(4)
    root.right = TreeNode(8)
    root.left.left = TreeNode(11)
    root.right.left = TreeNode(13)
    root.right.right = TreeNode(4)
    root.left.left.left = TreeNode(7)
    root.left.left.right = TreeNode(2)
    root.right.right.right = TreeNode(1)
    print(Solution().hasPathSum(root, 22))  # True

    # Example 2: root = [1,2,3], targetSum = 5
    root2 = TreeNode(1)
    root2.left = TreeNode(2)
    root2.right = TreeNode(3)
    print(Solution().hasPathSum(root2, 5))  # False

    # Example 3: root = [], targetSum = 0
    print(Solution().hasPathSum(None, 0))  # False


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - Iterative DFS (Stack)

Instead of using recursion, we use an explicit stack to perform depth-first traversal. Each entry in the stack stores a node and the remaining sum needed. When we reach a leaf node, we check if the remaining sum equals the leaf's value.

TimeComplexity: O(n)

SpaceComplexity: O(h)

""" 0112.2 - Path Sum - Solution 2 - Iterative DFS (Stack) """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional

#####################################################################################
# Classes
#####################################################################################
class TreeNode:
    """TreeNode Class"""

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


class Solution:
    """Solution Class"""

    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        """Path Sum Function"""
        if not root:
            return False

        stack = [(root, targetSum - root.val)]

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

            # Check if current node is a leaf with remaining sum == 0
            if not node.left and not node.right and remaining == 0:
                return True

            if node.right:
                stack.append((node.right, remaining - node.right.val))
            if node.left:
                stack.append((node.left, remaining - node.left.val))

        return False


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    # Example 1: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
    root = TreeNode(5)
    root.left = TreeNode(4)
    root.right = TreeNode(8)
    root.left.left = TreeNode(11)
    root.right.left = TreeNode(13)
    root.right.right = TreeNode(4)
    root.left.left.left = TreeNode(7)
    root.left.left.right = TreeNode(2)
    root.right.right.right = TreeNode(1)
    print(Solution().hasPathSum(root, 22))  # True

    # Example 2: root = [1,2,3], targetSum = 5
    root2 = TreeNode(1)
    root2.left = TreeNode(2)
    root2.right = TreeNode(3)
    print(Solution().hasPathSum(root2, 5))  # False

    # Example 3: root = [], targetSum = 0
    print(Solution().hasPathSum(None, 0))  # False


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

0112 - Path Sum

Solution 1 - Recursive DFS

Solution 2 - Iterative DFS (Stack)