Problem Statement in English

You’re given a binary tree. Your task is to determine if a root to leaf path exists such that the sum of nodes in the path results in the provided targetSum.

Approach

All we need to do is backtrack, or apply a depth first search. In order to do so we need to use a stack.

Each stack element is made up of 2 parts:

  • the last node we visited (index 0)
  • and the sum of nodes visited so far (index 1)

I’ve used the iterative solution, but I think the recursive one will be prettier with respect to this particular question.

Solution in Python


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


class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        # if the root is `None`, return `False`
        if not root:
            return False
        # check if the root's `val` is the target, if so, return `True`
        elif root.val == targetSum and not root.left and not root.right:
            return True

        # prepopulate the stack with `root` and its `val`
        stack = [[root, root.val]]

        # run while stack isn't empty
        while stack:
            # we use this to determine the position of the current node we're processing,
            # as once we add its left and right children, we need to remove it
            removeAt = -1

            # just to improve code readability
            top = stack[-1]
            topNode = top[0]
            topSum = top[1]

            # if the node we're processing has a valid `left` child
            if topNode.left:
                s = topSum
                # calculate what the sum will be if we include this node
                s += topNode.left.val

                # if `s` is the desired target
                if s == targetSum:
                    tempNode = topNode.left

                    # check if it's a leaf
                    if not tempNode.left and not tempNode.right:
                        # if so, we've found our answer
                        return True
                    else:
                        # else add this node and the current sum to the stack
                        stack.append([topNode.left, s])
                        # this is because we'll use python negative indexing
                        # to remove the parent of the left child
                        removeAt -= 1
                else:
                    # else add this node and the current sum to the stack
                    stack.append([topNode.left, s])
                    # this is because we'll use python negative indexing
                    # to remove the parent of the left child
                    removeAt -= 1

            # now we just do the same thing for the right child

            # if the node we're processing has a valid `right` child
            if topNode.right:
                s = topSum
                # calculate what the sum will be if we include this node
                s += topNode.right.val

                # if `s` is the desired target
                if s == targetSum:
                    tempNode = topNode.right

                    # check if it's a leaf
                    if not tempNode.left and not tempNode.right:
                        # if so, we've found our answer
                        return True
                    else:
                        # else add this node and the current sum to the stack
                        stack.append([topNode.right, s])
                        # this is because we'll use python negative indexing
                        # to remove the parent of the right child
                        removeAt -= 1
                else:
                    # else add this node and the current sum to the stack
                    stack.append([topNode.right, s])
                    # this is because we'll use python negative indexing
                    # to remove the parent of the right child
                    removeAt -= 1

            # use `removeAt` to remove the parent node we just finished processing
            stack.pop(removeAt)

        # if the stack's empty and we've reached here,
        # then the target doesn't exist
        return False

Complexity

  • Time: $O(n)$
    Since we process atmost $n$ nodes.

  • Space: $O(n)$
    Since we use a stack that can contain atmost $n$ nodes.

Mistakes I Made

I didn’t read the question properly, and failed to notice that we’re only supposed to return root to leaf paths whose sum is the desired target.

And we are done.