Path Sum

Patrick Leaton
Published: April 3, 2021, 4:38 a.m.
Problem Description

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

 

The description was taken from https://leetcode.com/problems/path-sum/.

Problem Solution

#Iterative
#O(N) Time, O(Log(N)) Space for Balanced Tree, O(N) for Unbalanced
class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root:
            return False
        stack = [(root, sum - root.val)]
        while stack:
            node, curr_sum = stack.pop()
            if not node.left and not node.right and curr_sum == 0: 
                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
 
#Recursive
#O(N) Time, O(Log(N)) Space for Balanced Tree, O(N) for Unbalanced
class Solution:
    def hasPathSum(self, root: TreeNode, curr_sum: int) -> bool:
        if not root:
            return False
        curr_sum -= root.val
        if not root.left and not root.right:  
            return curr_sum == 0
        return self.hasPathSum(root.left, curr_sum) or \
               self.hasPathSum(root.right, curr_sum)

Problem Explanation

Iterative Solution

Since an entire branch could be a path sum and not a portion of it, we don't need to do anything fancy.  We can traverse the tree with a Depth-First Search or Breadth-First Search and for each node, we will decrement the sum input by its value.  Once we get to leaf nodes, the nodes without children, we will see if the sum has been decremented the correct amount to be zero.  

Let's start by checking if the input root is null.  We will return false if it is because there would be no path.

        if not root:
            return False

 

Afterward, we will push the root onto the stack along with the value of the sum decremented by the root's value.

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

 

We will then create a loop that will run while there are still nodes on the stack left to process.

        while stack:

 

During each iteration, we will pop a node of the stack along with its current sum.

            node, curr_sum = stack.pop()

 

If we are at a leaf node and its current sum is zero, then we have a root to leaf path where the nodes along the path sum to the target.

We'll return true if this is the case.

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

 

Otherwise, we will push the children of the node onto the stack along with their current sums decremented by their values.

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

 

If we have processed each node and haven't found a valid path sum, we will return false.

        return False

Recursive Solution

The recursive solution is much shorter.  

We are still decrementing the sum and seeing if we have a leaf that has zeroed out the sum but instead of a stack, we will use a recursive call stack.  

Let's start by setting our base case.  If we have hit a leaf node, we will return and return from the bottom of this DFS path.

        if not root:
            return False

 

At the beginning of each recursive call, we will decrement the sum by the root's value.

        sum -= root.val

 

Next, we will check if we are at a leaf.

If we are at a leaf then we will check if our call has zeroed out the sum.

We will return true if it has.

        if not root.left and not root.right:  
            return sum == 0

 

If we don't have a path sum from our current node, we will recurse the function with the node's children to see if one of them has a path sum.

        return self.hasPathSum(root.left, sum) or \
               self.hasPathSum(root.right, sum)
 
This function will continue until we have traversed each sub-path or until we have found a root-to-leaf path where the values along the path sum to the target