Jobs

Interviews

Discussions

Path Sum II

Medium

Amazon

2 views

Topics:

TreesRecursion

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values.

A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: []

Example 3:

Input: root = [1,2], targetSum = 0
Output: []

Explain your approach. Discuss time and space complexity. What are some edge cases to consider?

Path Sum II

Medium

Amazon

2 views

Topics:

TreesRecursion

A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: []

Example 3:

Input: root = [1,2], targetSum = 0
Output: []

Explain your approach. Discuss time and space complexity. What are some edge cases to consider?

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 node values be negative, zero, or only positive?
What is the expected return value if the tree is empty, or if no paths sum to the targetSum?
What is the range of values for targetSum, and how does it relate to the potential sum of node values along a path?
Are we looking for *all* root-to-leaf paths that sum to targetSum, or is there a specific order they should be returned in if multiple paths exist?
Is the binary tree guaranteed to be balanced, or could it be highly unbalanced, potentially affecting stack space during recursion?

Brute Force Solution

Approach

The brute force method for the path sum problem involves exploring every possible path from the root of a tree to its leaves. We examine each path's sum to see if it matches the target sum, recording any paths that do. This method is exhaustive, guaranteeing that we find all valid paths.

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

Start at the very top of the tree, the root.
Consider the path that just includes the root node.
Now, for each branch extending from the root, add that node to the path and compute the sum of the nodes in the path.
If the sum equals the target, save that path.
If the sum doesn't equal the target, continue down that path, adding the next node on the branch.
Repeat this process, adding one node at a time to the path and checking the sum, until you reach a leaf node (a node with no children).
When you reach a leaf, check if the sum of the path from root to that leaf equals the target sum. If it does, save the path. If not, discard the path.
Do this for every single possible path in the tree, going down every branch from the root to every leaf.
In the end, you will have a collection of all the paths whose sums equal the target sum.

Code Implementation

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

def pathSumBruteForce(root, target_sum):
    all_valid_paths = []
    current_path = []

    def explore_paths(node, current_sum):
        if not node:
            return

        # Add the current node's value to the path
        current_path.append(node.value)
        current_sum += node.value

        # Check if it is a leaf node
        if not node.left and not node.right:
            if current_sum == target_sum:
                all_valid_paths.append(current_path[:])

        else:
            # Recursively explore the left and right subtrees
            explore_paths(node.left, current_sum)
            explore_paths(node.right, current_sum)

        # Backtrack: Remove the current node from the path
        current_sum -= current_path[-1]
        current_path.pop()

    explore_paths(root, 0)
    return all_valid_paths

Big(O) Analysis

Time Complexity

O(N*H) – The algorithm explores all possible root-to-leaf paths in the tree. In the worst-case scenario, where the tree is skewed (e.g., a linked list), we might have to traverse all N nodes for multiple paths. However, if the tree is balanced, the average path length would be closer to the height (H) of the tree. Therefore, in the worst case, the algorithm might potentially examine each node in the tree for all possible paths and makes a copy of them, but we really only iterate through the tree once in total, and for each node, we are examining at most the height, so this brings us to O(N*H) where N is the number of nodes and H is the height of the tree.

Space Complexity

O(N) – The space complexity is determined by the depth of the recursion and the space used to store the paths. In the worst-case scenario (e.g., a skewed tree), the recursion stack can grow to a depth of N, where N is the number of nodes in the tree. Additionally, we are storing paths, which in the worst case could have a length close to N. Therefore, the auxiliary space used to store the recursion stack and temporary paths is O(N).

Optimal Solution

Approach

The goal is to find all paths from the root of a tree to its leaves where the sum of the node values along the path equals a target value. We'll use a clever way to explore each path and keep track of the current sum as we go, avoiding unnecessary calculations.

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

Start at the root of the tree and create a list to hold the current path you're exploring and another list to save the paths that satisfy the condition.
As you move down the tree, keep track of the current sum by adding the value of each node you visit.
When you reach a leaf node (a node with no children), check if the current sum equals the target sum.
If the sum matches the target, save a copy of the current path in your list of valid paths.
Whether the sum matches or not, when you are done processing the leaf node, go back up the tree (backtrack) by removing the last node from the path and subtracting its value from the running sum.
Continue this process for all possible paths, exploring each branch of the tree.
The clever trick is that by updating the path and the sum as you go, you avoid redundant calculations and efficiently explore all possible paths without storing all combinations.

Code Implementation

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

def pathSum(root, target_sum):
    all_valid_paths = []
    current_path = []

    def traverseTree(node, current_sum):
        if not node:
            return

        current_path.append(node.value)
        current_sum += node.value

        # Check if the current node is a leaf node.
        if not node.left and not node.right:

            # If leaf node and current sum equals target sum,
            # then add the current path to result.
            if current_sum == target_sum:
                all_valid_paths.append(current_path[:])

        else:
            # Recursively traverse left and right subtrees.
            traverseTree(node.left, current_sum)
            traverseTree(node.right, current_sum)

        # Backtrack: remove current node and subtract
        # its value when returning to the parent node.
        current_sum -= node.value

        current_path.pop()

    # Initiate traversal from the root node.
    traverseTree(root, 0)

    return all_valid_paths

Big(O) Analysis

Time Complexity

O(n) – The algorithm visits each node in the tree once. In the worst-case scenario, we might have a skewed tree where we need to traverse n nodes (where n is the total number of nodes in the tree) from the root to a leaf. While building a new list to store each valid path when the target sum is found takes time proportional to the path length (which is at most n), the total number of valid paths will not, in the worst case, significantly increase the time complexity beyond O(n). The dominant factor remains the traversal of all nodes in the tree once, resulting in O(n) time complexity.

Space Complexity

O(N) – The auxiliary space complexity is determined by the size of the 'path' list and the recursion stack. In the worst-case scenario, the tree resembles a linked list, and the 'path' list could store all N nodes from the root to the leaf. Similarly, the recursion stack depth could also reach N in the worst case, corresponding to the height of the tree. Therefore, the space complexity is O(N), dominated by the potential size of the path and recursion stack.

Edge Cases

Case	How to Handle
Null root node	Return an empty list immediately as there are no paths.
Single node tree where node value equals targetSum	Return a list containing a list with the single node's value.
Single node tree where node value does NOT equal targetSum	Return an empty list as no path satisfies the condition.
Tree with only negative values and a negative targetSum	The algorithm should correctly traverse and identify paths that sum to the (negative) target.
Tree with large positive and negative values leading to potential integer overflow when summing the path	Use a data type (e.g., long) that can accommodate the larger potential sums to prevent overflow issues.
Tree with a path that sums to targetSum but is not a root-to-leaf path	Ensure the path ends at a leaf node (left and right children are null) to be considered a valid solution.
Multiple root-to-leaf paths that sum to targetSum	The solution must identify and store all such paths in the result list.
Deeply unbalanced tree potentially leading to stack overflow with recursion	While recursion is a common approach, be mindful of stack depth; iterative solutions with explicit stack management could prevent stack overflow in extremely deep trees.

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 node values be negative, zero, or only positive?
What is the expected return value if the tree is empty, or if no paths sum to the targetSum?
What is the range of values for targetSum, and how does it relate to the potential sum of node values along a path?
Are we looking for *all* root-to-leaf paths that sum to targetSum, or is there a specific order they should be returned in if multiple paths exist?
Is the binary tree guaranteed to be balanced, or could it be highly unbalanced, potentially affecting stack space during recursion?

Brute Force Solution

Approach

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

Start at the very top of the tree, the root.
Consider the path that just includes the root node.
Now, for each branch extending from the root, add that node to the path and compute the sum of the nodes in the path.
If the sum equals the target, save that path.
If the sum doesn't equal the target, continue down that path, adding the next node on the branch.
Repeat this process, adding one node at a time to the path and checking the sum, until you reach a leaf node (a node with no children).
When you reach a leaf, check if the sum of the path from root to that leaf equals the target sum. If it does, save the path. If not, discard the path.
Do this for every single possible path in the tree, going down every branch from the root to every leaf.
In the end, you will have a collection of all the paths whose sums equal the target sum.

Code Implementation

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

def pathSumBruteForce(root, target_sum):
    all_valid_paths = []
    current_path = []

    def explore_paths(node, current_sum):
        if not node:
            return

        # Add the current node's value to the path
        current_path.append(node.value)
        current_sum += node.value

        # Check if it is a leaf node
        if not node.left and not node.right:
            if current_sum == target_sum:
                all_valid_paths.append(current_path[:])

        else:
            # Recursively explore the left and right subtrees
            explore_paths(node.left, current_sum)
            explore_paths(node.right, current_sum)

        # Backtrack: Remove the current node from the path
        current_sum -= current_path[-1]
        current_path.pop()

    explore_paths(root, 0)
    return all_valid_paths

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start at the root of the tree and create a list to hold the current path you're exploring and another list to save the paths that satisfy the condition.
As you move down the tree, keep track of the current sum by adding the value of each node you visit.
When you reach a leaf node (a node with no children), check if the current sum equals the target sum.
If the sum matches the target, save a copy of the current path in your list of valid paths.
Whether the sum matches or not, when you are done processing the leaf node, go back up the tree (backtrack) by removing the last node from the path and subtracting its value from the running sum.
Continue this process for all possible paths, exploring each branch of the tree.
The clever trick is that by updating the path and the sum as you go, you avoid redundant calculations and efficiently explore all possible paths without storing all combinations.

Code Implementation

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

def pathSum(root, target_sum):
    all_valid_paths = []
    current_path = []

    def traverseTree(node, current_sum):
        if not node:
            return

        current_path.append(node.value)
        current_sum += node.value

        # Check if the current node is a leaf node.
        if not node.left and not node.right:

            # If leaf node and current sum equals target sum,
            # then add the current path to result.
            if current_sum == target_sum:
                all_valid_paths.append(current_path[:])

        else:
            # Recursively traverse left and right subtrees.
            traverseTree(node.left, current_sum)
            traverseTree(node.right, current_sum)

        # Backtrack: remove current node and subtract
        # its value when returning to the parent node.
        current_sum -= node.value

        current_path.pop()

    # Initiate traversal from the root node.
    traverseTree(root, 0)

    return all_valid_paths

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null root node	Return an empty list immediately as there are no paths.
Single node tree where node value equals targetSum	Return a list containing a list with the single node's value.
Single node tree where node value does NOT equal targetSum	Return an empty list as no path satisfies the condition.
Tree with only negative values and a negative targetSum	The algorithm should correctly traverse and identify paths that sum to the (negative) target.
Tree with large positive and negative values leading to potential integer overflow when summing the path	Use a data type (e.g., long) that can accommodate the larger potential sums to prevent overflow issues.
Tree with a path that sums to targetSum but is not a root-to-leaf path	Ensure the path ends at a leaf node (left and right children are null) to be considered a valid solution.
Multiple root-to-leaf paths that sum to targetSum	The solution must identify and store all such paths in the result list.
Deeply unbalanced tree potentially leading to stack overflow with recursion	While recursion is a common approach, be mindful of stack depth; iterative solutions with explicit stack management could prevent stack overflow in extremely deep trees.