< Back




112. Path Sum

Given the root of a binary tree, we're asked to return True or False if a path exists in the binary
tree where the value of the nodes sum to some targetSum. We can use DFS to create the path, and at
each node we'll keep track of the targetSum less the values of the nodes previously visited.

If the currSum == 0 when we visit a node, we know that we've discovered a path that sums to the
targetSum and we can return True. Another contstaint is that both the left and right nodes have to
be empty.

The solution is as follows:


  class Solution:
      def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
          if not root:
              return False

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

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

              if not node.left and not node.right and currSum == 0:
                  return True
              if node.right:
                  stack.append((node.right, currSum - node.right.val))
              if node.left:
                  stack.append((node.left, currSum - node.left.val))

          return False


_ Time Complexity:

  O(n) - We inspect all nodes in the binary tree.

_ Space Complexity:

  O(n) - We maintain a stack of nodes to explore.