Jobs

Interviews

Discussions

Two Sum IV - Input is a BST

Easy

Amazon

4 views

Topics:

TreesBinary SearchTwo PointersRecursion

Given the root of a binary search tree and an integer k, determine whether there exist two elements in the BST such that their sum is equal to k. If such elements exist, return true; otherwise, return false.

Consider these examples:

Example 1:

Input: root = [5,3,6,2,4,null,7], k = 9
Output: true (because 2 + 7 = 9 or 3 + 6 = 9 or 4 + 5 = 9).

Example 2:

Input: root = [5,3,6,2,4,null,7], k = 28
Output: false

Clarifications:

What should I return if the BST is empty?
What should I return if the BST contains only one node?
Is the input always a valid BST?
What is the range of node values and k?
Is there a most optimal solution better than O(n)?

Two Sum IV - Input is a BST

Easy

Amazon

4 views

Topics:

TreesBinary SearchTwo PointersRecursion

Consider these examples:

Example 1:

Input: root = [5,3,6,2,4,null,7], k = 9
Output: true (because 2 + 7 = 9 or 3 + 6 = 9 or 4 + 5 = 9).

Example 2:

Input: root = [5,3,6,2,4,null,7], k = 28
Output: false

Clarifications:

What should I return if the BST is empty?
What should I return if the BST contains only one node?
Is the input always a valid BST?
What is the range of node values and k?
Is there a most optimal solution better than O(n)?

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:

What is the range of values for the nodes in the BST, and can the target value k be negative?
Can the BST be empty, or contain only one node?
Are there any duplicate values allowed in the BST? If so, are we looking for distinct *nodes* that sum to k, or distinct *values*?
If multiple pairs of nodes sum to k, is it sufficient to return true as soon as the first such pair is found?
What is the expected size of the tree, and is the tree guaranteed to be balanced?

Brute Force Solution

Approach

The brute force approach to solving this problem involves checking every possible pair of numbers in the binary search tree to see if they add up to the target value. It's like trying every combination of two numbers until you find the right one. This is a straightforward, though not very efficient, method.

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

Get a list of all the numbers stored in the tree.
Pick the first number from the list.
Then, for every other number in the list, add it to the first number.
Check if the sum equals the target value.
If the sum equals the target, you've found a solution, so you're done.
If not, move on to the next number in the list and repeat the addition and checking steps.
Do this for every number in the list as the first number.
If you go through all the possibilities and don't find a pair that adds up to the target, there is no solution.

Code Implementation

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

def find_target_brute_force(root, target_value):
    def inorder_traversal(node, numbers_list):
        if not node:
            return
        inorder_traversal(node.left, numbers_list)
        numbers_list.append(node.val)
        inorder_traversal(node.right, numbers_list)

    numbers = []
    inorder_traversal(root, numbers)

    # Iterate through all possible pairs
    for first_index in range(len(numbers)):
        for second_index in range(first_index + 1, len(numbers)):
            # Check if the current pair sums to the target
            if numbers[first_index] + numbers[second_index] == target_value:
                return True

    # If no pair is found after checking all combinations
    return False

Big(O) Analysis

Time Complexity

O(n²) – The described brute force approach first extracts all n nodes from the BST into a list. The algorithm then iterates through this list, comparing each element with every other element to check if their sum equals the target. This involves a nested loop structure where, for each of the n elements, we potentially iterate through the remaining n-1 elements. Therefore, the time complexity is proportional to n * (n-1), which simplifies to O(n²).

Space Complexity

O(N) – The brute force approach first requires storing all the numbers from the binary search tree into a list. If the binary search tree contains N nodes, then this list will contain N elements. The algorithm then iterates through this list, performing pairwise sums, but this iteration does not require any additional data structures that scale with the input size beyond the initial list. Therefore, the auxiliary space complexity is O(N).

Optimal Solution

Approach

The key to solving this problem efficiently is to convert the tree into an ordered sequence of numbers. Then, we can use a two-pointer technique to efficiently find a pair of numbers that sum up to the target value.

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

First, transform the tree into a sorted list of numbers. You can achieve this by traversing the tree in a special way (called in-order traversal), which ensures you visit the nodes in ascending order.
Next, use two 'pointers,' one starting at the beginning of the list (smallest number) and the other at the end (largest number).
Add the numbers that the two pointers are pointing to.
If the sum is equal to the target value, you've found your pair! Return true.
If the sum is less than the target value, move the left pointer to the right (towards larger numbers) to increase the sum.
If the sum is greater than the target value, move the right pointer to the left (towards smaller numbers) to decrease the sum.
Repeat steps 3-6 until the two pointers meet. If you reach this point without finding a pair, it means no such pair exists in the tree, so return false.

Code Implementation

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

def findTarget(root, k):
    sorted_list = []

    def inOrderTraversal(node):
        if not node:
            return
        inOrderTraversal(node.left)
        sorted_list.append(node.val)
        inOrderTraversal(node.right)

    inOrderTraversal(root)

    left_pointer = 0
    right_pointer = len(sorted_list) - 1

    while left_pointer < right_pointer:
        current_sum = sorted_list[left_pointer] + sorted_list[right_pointer]

        # We found the target
        if current_sum == k:
            return True

        if current_sum < k:
            # Need a larger sum, move left pointer.
            left_pointer += 1

        else:
            # Need a smaller sum, move right pointer.
            right_pointer -= 1

    # No such pair found
    return False

Big(O) Analysis

Time Complexity

O(n) – The in-order traversal of the BST takes O(n) time, where n is the number of nodes in the tree, because each node is visited exactly once. The two-pointer approach iterates through the sorted list, comparing pairs and adjusting pointers, which takes at most O(n) time since each pointer moves towards the middle at most n times in total. Therefore, the overall time complexity is dominated by the linear time operations of the in-order traversal and two-pointer search, resulting in O(n) + O(n) which simplifies to O(n).

Space Complexity

O(N) – The primary space complexity comes from storing the BST nodes in a sorted list during the in-order traversal, resulting in an auxiliary list of size N, where N is the number of nodes in the BST. The two-pointer technique itself uses constant space. Therefore, the dominant space usage is determined by the size of the list created from the BST. In addition to the list, recursive calls for the in-order traversal contribute to the call stack. In the worst-case of a skewed tree, the recursion depth can be N, thus contributing O(N) space. Considering the space for both the sorted list and recursion stack, the overall space complexity is O(N).

Edge Cases

Case	How to Handle
Root is null	Return false immediately since there are no nodes to sum.
BST contains only one node	Return false immediately since we need two distinct nodes.
All nodes in the BST have the same value	The algorithm must ensure that two different nodes are used for the sum, even if their values are identical.
No two nodes sum to the target	The algorithm should correctly return false when no such pair exists in the BST.
BST with large depth leading to potential stack overflow with recursive approaches	Consider an iterative approach (e.g., using a stack or in-order traversal with two pointers) to avoid stack overflow.
Integer overflow when summing node values	Use a data type with a larger range (e.g., long) when summing to prevent potential overflow.
Target value is extremely large or small	The chosen data type must be able to accommodate the target value to avoid unexpected behavior.
BST contains negative numbers, zero, and positive numbers	The algorithm should function correctly regardless of the sign or value of the nodes.

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:

What is the range of values for the nodes in the BST, and can the target value k be negative?
Can the BST be empty, or contain only one node?
Are there any duplicate values allowed in the BST? If so, are we looking for distinct *nodes* that sum to k, or distinct *values*?
If multiple pairs of nodes sum to k, is it sufficient to return true as soon as the first such pair is found?
What is the expected size of the tree, and is the tree guaranteed to be balanced?

Brute Force Solution

Approach

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

Get a list of all the numbers stored in the tree.
Pick the first number from the list.
Then, for every other number in the list, add it to the first number.
Check if the sum equals the target value.
If the sum equals the target, you've found a solution, so you're done.
If not, move on to the next number in the list and repeat the addition and checking steps.
Do this for every number in the list as the first number.
If you go through all the possibilities and don't find a pair that adds up to the target, there is no solution.

Code Implementation

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

def find_target_brute_force(root, target_value):
    def inorder_traversal(node, numbers_list):
        if not node:
            return
        inorder_traversal(node.left, numbers_list)
        numbers_list.append(node.val)
        inorder_traversal(node.right, numbers_list)

    numbers = []
    inorder_traversal(root, numbers)

    # Iterate through all possible pairs
    for first_index in range(len(numbers)):
        for second_index in range(first_index + 1, len(numbers)):
            # Check if the current pair sums to the target
            if numbers[first_index] + numbers[second_index] == target_value:
                return True

    # If no pair is found after checking all combinations
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, transform the tree into a sorted list of numbers. You can achieve this by traversing the tree in a special way (called in-order traversal), which ensures you visit the nodes in ascending order.
Next, use two 'pointers,' one starting at the beginning of the list (smallest number) and the other at the end (largest number).
Add the numbers that the two pointers are pointing to.
If the sum is equal to the target value, you've found your pair! Return true.
If the sum is less than the target value, move the left pointer to the right (towards larger numbers) to increase the sum.
If the sum is greater than the target value, move the right pointer to the left (towards smaller numbers) to decrease the sum.
Repeat steps 3-6 until the two pointers meet. If you reach this point without finding a pair, it means no such pair exists in the tree, so return false.

Code Implementation

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

def findTarget(root, k):
    sorted_list = []

    def inOrderTraversal(node):
        if not node:
            return
        inOrderTraversal(node.left)
        sorted_list.append(node.val)
        inOrderTraversal(node.right)

    inOrderTraversal(root)

    left_pointer = 0
    right_pointer = len(sorted_list) - 1

    while left_pointer < right_pointer:
        current_sum = sorted_list[left_pointer] + sorted_list[right_pointer]

        # We found the target
        if current_sum == k:
            return True

        if current_sum < k:
            # Need a larger sum, move left pointer.
            left_pointer += 1

        else:
            # Need a smaller sum, move right pointer.
            right_pointer -= 1

    # No such pair found
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Root is null	Return false immediately since there are no nodes to sum.
BST contains only one node	Return false immediately since we need two distinct nodes.
All nodes in the BST have the same value	The algorithm must ensure that two different nodes are used for the sum, even if their values are identical.
No two nodes sum to the target	The algorithm should correctly return false when no such pair exists in the BST.
BST with large depth leading to potential stack overflow with recursive approaches	Consider an iterative approach (e.g., using a stack or in-order traversal with two pointers) to avoid stack overflow.
Integer overflow when summing node values	Use a data type with a larger range (e.g., long) when summing to prevent potential overflow.
Target value is extremely large or small	The chosen data type must be able to accommodate the target value to avoid unexpected behavior.
BST contains negative numbers, zero, and positive numbers	The algorithm should function correctly regardless of the sign or value of the nodes.