Path Sum In Binary Tree

Difficulty: Easy

Asked in: Amazon, Microsoft, Yahoo

Understanding the problem

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

Problem Note

A leaf is a node with no children.

Example 1

Input: Given the below binary tree and sum = 22
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \      \
7    2      1
Output: true
Explanation: There exist a root-to-leaf path 5->4->11->2 which sum is 22.

The node structure passed to your function will be

class TreeNode
{
    int val
    TreeNode left
    TreeNode right
}

Solutions

Recursive DFS solution: Make a DFS traversal while passing the sum through “call by value” and reduce the sum by the node value. Return true if sum becomes zero at any leaf node.
Iterative Approach using Queue: Add all nodes to a queue and store the sum value of each node to another queue. When it is a leaf node, check the stored sum value.

You may try to solve the problem here: Path sum in a binary tree

Learning via problem-solving is the best way to crack any interview!

1. Recursive DFS Solution

This problem could be solved by making a simple DFS or preorder traversal through the tree. If you will think that, all we have to do is to check if any path from the root to any leaf will sum up to the given sum .

Example →

Let's consider the above example, there are many paths like 5->4->11->7 or 5->4->11->2 and so on. This seems like a simple preorder traversal in which we will perform some check on the root node, then recursively go to the left subtree and after checking all the left subtree, we go to the right subtree.

In this case, If we will try to think of a similar way of traversal with passing another argument, i.e. sum with every level of traversal, its value decreases by the root value of that subtree, then all we have to check if the leaf node is equal to the sum at that state, If that is so, then return True otherwise return False.

Solution Steps

If root is null return false
Subtract rootnode.val from the given sum to get new sum

now make two recursive calls for both left and right for the root node

3. if the root node visited is a leaf node and its value is equal to the new sum then return true

Pseudo Code

int pathSumExists(TreeNode root, int sum) {
    if(root is NULL) 
    {
        return false
    }
    if(root.val == sum and root.left is NULL and root.right is NULL)
    {
        return true
    }       
    return pathSumExists(root.left, sum - root.val) or  pathSumExists(root.right, sum - root.val)
    }

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n) (How?)

Critical Ideas to Think

How did we check a leaf node?
How does the leaf node become equal to the sum, if the path traversed is a valid path?

2. Iterative Approach Using Queue

If you understood how the recursive approach is working behind the hood, then you can clone the similar procedure into the iteration.

There are two ways in which you can do that

Either by modifying the value of the nodes in the tree iteratively using Queue. Each node will store the sum from the root node of the tree up to that node. All we have to check if any leaf node is equal to the given sum.
Creating two queues, First will be used to make the traversals iteratively through the tree and the second will store the sum up to that node from the root corresponding to the changes in the first queue.

Solution Step

Make an iterative traversal through the tree using a Queue of tree nodes. ( refer here )
Maintain another Queue of integers that perform the same operations as the first queue of tree nodes.
The integer queue will store the value from the root node to the current node corresponding to the tree node queue.
At any point, the current node becomes the leaf node and the corresponding Integer queue’s popped value is equal to the sum , then return True.

Pseudo Code

Using Two Queues

bool pathSumExists(TreeNode root, int sum) {
    if(root is null) 
        return false 
    // Queue of tree node
    Queue nodes
    // Queue of Integers 
    Queue values
    nodes.add(root)
    values.add(root.val) 
    while(nodes is not empty) {
        TreeNode curr = nodes.front()
        nodes.pop()
        sumValue = values.front()
        values.pop()
        if(curr.left is null and curr.right is null and sumValue==sum){
            return true
        }
        if(curr.left is not null){
            nodes.add(curr.left)
            values.add(sumValue + curr.left.val)
        }
        if(curr.right is not null){
            nodes.add(curr.right)
            values.add(sumValue+curr.right.val)
        }
    }
    return false
}

By modifying the tree nodes.

bool pathSumExists(TreeNode root, int sum){
    if(root is NULL)  
        return false
    // Queue of treenode
    queue nodes
    nodes.add(root)
    while(nodes is not empty){
        TreeNode curr = nodes.front()
        nodes.pop()
        if(curr.left is NULL and curr.right is NULL){
            if(curr.val == sum)
                return true
        }
        if(curr.left){
            curr.left.val = curr.left.val + curr.val
            nodes.push(curr.left)
        }
        if(curr.right){
            curr.right.val = curr.right.val + curr.val
            nodes.push(curr.right)
        }
    }
    return false
}

Complexity Analysis

Time Complexity: O(N)

Space Complexity: O(N)

Critical Ideas to Think

What is the difference between the two iterative approaches discussed above?
How we are traversing through the tree iteratively?
Is it important to use two queues if we are not liable to change the values of the tree nodes? If yes, Why?