Path Sum

Easy

Amazon

1 view

Topics:

TreesRecursion

Given the root of a binary tree and an integer targetSum, determine if there exists a root-to-leaf path such that the sum of all values along the path equals targetSum.

A leaf is defined as a node with no children.

Example 1: Consider the following binary tree:

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

If targetSum = 22, the function should return true because the path 5 -> 4 -> 11 -> 2 sums to 22.

Example 2:

For the tree:

  1
 / \
2   3

If targetSum = 5, the function should return false because the paths 1 -> 2 (sum is 3) and 1 -> 3 (sum is 4) do not equal 5.

Example 3:

If root = [] (an empty tree) and targetSum = 0, the function should return false because there are no root-to-leaf paths.

Constraints:

The number of nodes in the tree is in the range [0, 5000].
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

Write a function to efficiently solve this problem. Consider edge cases like an empty tree or a tree with a single node.

Path Sum

Easy

Amazon

1 view

Topics:

TreesRecursion

Given the root of a binary tree and an integer targetSum, determine if there exists a root-to-leaf path such that the sum of all values along the path equals targetSum.

A leaf is defined as a node with no children.

Example 1: Consider the following binary tree:

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

If targetSum = 22, the function should return true because the path 5 -> 4 -> 11 -> 2 sums to 22.

Example 2:

For the tree:

  1
 / \
2   3

If targetSum = 5, the function should return false because the paths 1 -> 2 (sum is 3) and 1 -> 3 (sum is 4) do not equal 5.

Example 3:

If root = [] (an empty tree) and targetSum = 0, the function should return false because there are no root-to-leaf paths.

Constraints:

The number of nodes in the tree is in the range [0, 5000].
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

Write a function to efficiently solve this problem. Consider edge cases like an empty tree or a tree with a single node.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the tree contain negative node values?
What should I return if no path sums to the target sum?
Is the provided tree guaranteed to be a binary search tree, or can it be a more general binary tree?
By 'path', do you mean a path from the root to a leaf, or can the path start and end at any nodes within the tree?
Is it possible for the tree to be empty (null root), and if so, what is the expected behavior?

Brute Force Solution

Approach

We're given a tree and a target number, and we want to find if there's a path from the top of the tree to a leaf where the numbers along the path add up to the target. The brute force approach explores every single possible path from the top to the bottom of the tree.

Here's how the algorithm would work step-by-step:

Start at the very top of the tree.
Consider one possible path by moving to one of its children.
Keep going down the tree, always picking one of the children, until you reach the end of a path (a 'leaf').
When you get to the end, add up all the numbers you encountered along that path.
Check if the sum is equal to the target number. If it is, you've found a solution!
If the sum isn't the target number, or you've already explored one direction, go back and try a different path, going to the other child instead.
Repeat this process of exploring every possible path until you've checked every single route from the top to a leaf.

Code Implementation

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

def hasPathSumBruteForce(root, targetSum):
    if not root:
        return False

    def pathSumHelper(node, currentSum):
        currentSum += node.val

        # We have reached a leaf node
        if not node.left and not node.right:
            return currentSum == targetSum

        # Recursively check if the path exists in the left subtree
        if node.left:

            if pathSumHelper(node.left, currentSum):
                return True

        # Recursively check if the path exists in the right subtree
        if node.right:

            if pathSumHelper(node.right, currentSum):
                return True

        return False

    return pathSumHelper(root, 0)

Big(O) Analysis

Time Complexity

O(n) – The algorithm traverses all possible paths from the root to each leaf node in the binary tree. In the worst-case scenario, the tree is a complete binary tree. This implies that we visit each node once. Since there are n nodes in the tree, where n is the number of nodes, the time complexity is proportional to the number of nodes visited. Therefore, the time complexity of the algorithm is O(n).

Space Complexity

O(H) – The space complexity is determined by the maximum depth of the recursion, which is proportional to the height (H) of the tree. In the worst case, the tree can be skewed, resembling a linked list, where H would be equal to N (the number of nodes). Each recursive call adds a new frame to the call stack to store local variables, representing the current path sum. Therefore, the auxiliary space used is O(H), or O(N) in the worst case of a skewed tree.

Optimal Solution

Approach

The best way to solve this problem involves exploring the tree in a systematic way while keeping track of the running sum. The core idea is to check, at each step, if we've reached a leaf node and if the current sum matches the target.

Here's how the algorithm would work step-by-step:

Start at the very top of the tree (the root).
As you move down the tree to a node, add the node's value to the running sum.
When you reach a node that has no children (a leaf node), check if the current running sum is equal to the target sum.
If the sum matches the target, you've found a path that works!
If the sum doesn't match the target, it's not a valid path, so you'll need to explore other paths.
To explore other paths, go back up the tree (backtrack) and subtract the node's value from the running sum as you go back up.
Continue exploring all possible paths down the tree until you've checked every potential route.

Code Implementation

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

def has_path_sum(root, target_sum):
    def path_sum_recursive(node, current_sum):
        if not node:
            return False

        current_sum += node.value

        # Check if it's a leaf node.
        if not node.left and not node.right:

            # If leaf node, compare running sum to target.
            if current_sum == target_sum:
                return True
            else:
                return False

        # Explore left and right subtrees.
        left_path = path_sum_recursive(node.left, current_sum)
        right_path = path_sum_recursive(node.right, current_sum)

        # Return true if either path is true
        return left_path or right_path

    return path_sum_recursive(root, 0)

Big(O) Analysis

Time Complexity

O(n) – The algorithm visits each node in the binary tree at most once. In the worst-case scenario, the algorithm explores all n nodes in the tree to determine if a path exists that sums to the target value. The operations performed at each node (addition, comparison) take constant time. Therefore, the time complexity is directly proportional to the number of nodes, resulting in O(n).

Space Complexity

O(H) – The space complexity is primarily determined by the recursion depth, where H represents the height of the binary tree. In the worst-case scenario, such as a skewed tree, the recursion depth can reach N (where N is the number of nodes), leading to N function calls on the stack. Therefore, the auxiliary space used by the call stack in the worst case is O(N). However, in a balanced tree, the height would be log N, so the space complexity becomes O(log N). We consider the height, H, so O(H) accurately describes space usage.

Edge Cases

Case	How to Handle
Null or empty tree root	Return false immediately, as there is no path to sum.
Single node tree where the node's value equals the target sum	Return true, as the single node constitutes a valid path.
Tree with only one path that sums to target	The algorithm should correctly identify this single valid path.
Tree with negative node values and a negative target sum	The algorithm should correctly handle negative values and sums, ensuring accurate path calculation.
Tree with very large positive/negative values that could cause integer overflow when summed	Use long data type to store the intermediate sum during path traversal to avoid integer overflow, if needed.
Tree with no path that sums to target (all paths exceed or fall short)	The algorithm should traverse all paths and return false if no path equals the target sum.
Tree with multiple paths that sum to target, only one path is necessary (path existence)	The algorithm should return true upon finding the first valid path.
Deeply unbalanced tree leading to stack overflow in recursive implementations	Consider iterative DFS or BFS approach with a stack to avoid stack overflow issues with extremely deep trees.