Leetcode: Path Sum

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.

For 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.

Understand the problem:
As described by the problem, given a binary tree and a sum, find a path from root to leaf such that adding up all the values along the path equals to the given sum. Return true if exists such a path, false otherwise. There are several points to take care in order to understand the problem accurately. 

• The tree is just a binary tree, not BST
• Values of the nodes could be either positive, zero or negative

We can take several examples to understand the problem.

For the null tree, return false since it never exists a path sum equals to a specific value.
      1
     /  \
   2    3
  /  \   /  \
4   5 6   7

Sum = 11, return true, since 1 -> 3 -> 7


Recursive Solution:
It is not hard to think about the pre-order traversal, since the problem requires the sum from root to leaf. So the basic idea is to traverse the binary tree pre-order and sum up the values. If the node is the leaf node and the path sum equals to the target sum, it returns true. Else, recursively find its right children and repeat the process. 

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;
        
        return preOrderTraversal(root, 0, sum);
    }
    
    private boolean preOrderTraversal(TreeNode root, int pathSum, int sum) {
        if (root == null) return false;
        
        pathSum += root.val;
        
        // at leaves
        if (root.left == null && root.right == null) {
            if (pathSum == sum) return true;
            else return false;
        }
        
        if (preOrderTraversal(root.left, pathSum, sum) == true) {
            return true;
        }
        
        if (preOrderTraversal(root.right, pathSum, sum) == true) {
            return true;
        }
        
        return false;
    }
}

Discussion:
Note that the path sum should be passed to its left and right child as a parameter, other than saving it as a global instance variable. The following code is wrong:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int pathSum = 0;
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;
        
        return preOrderTraversal(root, sum);
    }
    
    private boolean preOrderTraversal(TreeNode root, int sum) {
        if (root == null) return false;
        
        pathSum += root.val;
        
        // at leaves
        if (root.left == null && root.right == null) {
            if (pathSum == sum) return true;
            else return false;
        }
        
        if (preOrderTraversal(root.left, sum) == true) {
            return true;
        }
        
        if (preOrderTraversal(root.right, sum) == true) {
            return true;
        }
        
        return false;
    }
}

So why the code above is wrong. That is because when we reach to a leaf and return back to its parent, we should minus the value of its left child. If we maintain a global variable to store the path sum, even we return to the parent, the path sum will still be accumulated, which is wrong. 

For the complexity of the solution above, again its time complexity is O(n) since we traverse the tree only once. The space complexity is O(h) where h is the height of the tree due to the recursive method. 


Iterative Solution:
Similar to the pre-order traversal, the iterative solution still utilizes a stack. However, we should use another stack to store the partial sum until this node. For a node popped from the stack, if it is the leaf node and the partial sum equals to the target, return true. If the node has left or right child, we push them into the stack and push the path sum of the node into the stack as well. 

Code (Java):

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;
        
        Stack<TreeNode> nodeStack = new Stack<TreeNode>();
        Stack<Integer> sumStack = new Stack<Integer>();
        
        nodeStack.push(root);
        sumStack.push(root.val);
        
        while (!nodeStack.empty()) {
            TreeNode curr = nodeStack.pop();
            int pathSum = sumStack.pop();
            
            if (curr.left == null && curr.right == null && pathSum == sum)
                return true;
            
            if (curr.right != null) {
                nodeStack.push(curr.right);
                sumStack.push(pathSum + curr.right.val);
            }
            
            if (curr.left != null) {
                nodeStack.push(curr.left);
                sumStack.push(pathSum + curr.left.val);
            }
        }
        return false;
    }
}

Summary:
In this post, we learned the path sum using both recursive and iterative approach. For the corresponding iterative approach, a rule-of-thumb is to carefully think about how the recursive solution works. It will help you develop the iterative approach. Otherwise, just extending the iterative code of BFS or DFS will not simply work.