Jobs

Interviews

Discussions

Two Sum BSTs

Medium

Asked by:

5 views

Topics:

TreesBinary SearchTwo Pointers

Given two binary search trees, root1 and root2, return true if and only if there is a node in the first tree and a node in the second tree whose values sum up to a given integer target.

Example 1:

Input: root1 = [2,1,4], root2 = [1,0,3], target = 5
Output: true
Explanation: 2 + 3 = 5.

Example 2:

Input: root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18
Output: false

Constraints:

The number of nodes in each tree is in the range [1, 5000].
-10⁴ <= Node.val <= 10⁴
target is an integer in the range [-10⁵, 10⁵].

Try coding it in LeetCode

Two Sum BSTs

Medium

Asked by:

5 views

Topics:

TreesBinary SearchTwo Pointers

Given two binary search trees, root1 and root2, return true if and only if there is a node in the first tree and a node in the second tree whose values sum up to a given integer target.

Example 1:

Input: root1 = [2,1,4], root2 = [1,0,3], target = 5
Output: true
Explanation: 2 + 3 = 5.

Example 2:

Input: root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18
Output: false

Constraints:

The number of nodes in each tree is in the range [1, 5000].
-10⁴ <= Node.val <= 10⁴
target is an integer in the range [-10⁵, 10⁵].

Try coding it in LeetCode

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 are the possible ranges for node values in the BSTs? Could they be negative, zero, or very large?
Could either of the BSTs be empty or contain only a single node?
If there are multiple pairs across the two BSTs that sum to the target, should I return `true` as soon as I find one, or do I need to find all possible pairs (and if so, how should I return them)?
Are the BSTs guaranteed to be valid BSTs, or do I need to perform validation as part of my solution?
Is there a specific memory constraint I should be aware of, considering I might need to store nodes during traversal?

Brute Force Solution

Approach

The brute force method to solve this problem is to check every single possible pair of numbers, one from each tree. We want to see if any of those pairs add up to our target value. This guarantees we will find the answer if it exists, but it might take a very long time.

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

Take each number from the first tree, one at a time.
For each of those numbers, go through every single number in the second tree.
For each pair of numbers (one from the first tree and one from the second tree), add them together.
See if the sum of the pair is equal to the target value that we are looking for.
If we find a pair that adds up to the target, we have found our answer. We can stop looking.
If we go through every possible pair and don't find a sum that equals the target, then no such pair exists in the two trees.

Code Implementation

def two_sum_bsts_brute_force(root_one, root_two, target_value):
    # Convert BST one to a list
    first_tree_values = []
    def inorder_traversal_one(node):
        if node:
            inorder_traversal_one(node.left)
            first_tree_values.append(node.val)
            inorder_traversal_one(node.right)

    inorder_traversal_one(root_one)

    # Convert BST two to a list
    second_tree_values = []
    def inorder_traversal_two(node):
        if node:
            inorder_traversal_two(node.left)
            second_tree_values.append(node.val)
            inorder_traversal_two(node.right)

    inorder_traversal_two(root_two)

    # Iterate through all possible pairs
    for first_tree_value in first_tree_values:
        # Check every node in the second tree.
        for second_tree_value in second_tree_values:

            # We found our match
            if first_tree_value + second_tree_value == target_value:
                return True

    # If no pair sums to the target, return False
    return False

Big(O) Analysis

Time Complexity

O(n*m) – The algorithm iterates through each node in the first BST, which contains 'n' nodes. For each of these 'n' nodes, the algorithm iterates through every node in the second BST, which contains 'm' nodes, checking if their sum equals the target value. Therefore, the total number of operations is proportional to n multiplied by m. Thus, the time complexity is O(n*m).

Space Complexity

O(1) – The brute force algorithm iterates through each node in the first tree and compares it with every node in the second tree to find a pair summing to the target. The plain English explanation doesn't introduce auxiliary data structures that scale with input size. Thus, the space complexity is dominated by a few constant variables for tracking the current node from each tree during comparisons. Therefore, the space complexity is O(1), constant space.

Optimal Solution

Approach

The problem asks us to find if there's a pair of numbers, one from each of two special trees, that add up to a target value. The best way to solve this efficiently is to change one of the trees into an easy-to-search structure, then quickly check if the complement of each value in the other tree exists in this searchable structure.

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

Transform the first tree into a simple collection that lets you quickly check if a number is present.
Visit each number in the second tree, one by one.
For each number you find in the second tree, calculate what other number would be needed to reach the target sum.
Check if that 'needed' number is in the collection you created from the first tree.
If you find the 'needed' number, you've found your pair, and you're done!
If you go through all the numbers in the second tree and never find the 'needed' number in the first tree's collection, then no such pair exists.

Code Implementation

def find_target_in_two_bsts(root1, root2, target_value):

    # Convert the first BST into a set for fast lookups.
    tree1_values = set()
    def inorder_traversal_tree1(node):
        if node:
            inorder_traversal_tree1(node.left)
            tree1_values.add(node.val)
            inorder_traversal_tree1(node.right)
    inorder_traversal_tree1(root1)

    def inorder_traversal_tree2(node):
        if node:
            # Explore the left subtree
            inorder_traversal_tree2(node.left)

            # Calculate the complement needed from the first tree.
            complement = target_value - node.val

            # Check if the complement exists in the set from tree1.
            if complement in tree1_values:
                return True

            # Explore the right subtree
            if inorder_traversal_tree2(node.right):
                return True

        return False

    # Initiate the search on the second tree, given the set of the first tree
    return inorder_traversal_tree2(root2)

Big(O) Analysis

Time Complexity

O(n) – We transform the first BST into a hash set which takes O(n) time, where n is the number of nodes in the first tree. Then, we iterate through the second BST, performing a lookup in the hash set for each node. Since hash set lookups take O(1) on average, and we visit at most m nodes in the second tree (where m is the number of nodes in the second tree), this step takes O(m) time. The overall time complexity is thus O(n + m), where n is the number of nodes in the first tree and m is the number of nodes in the second tree. If we assume that the number of nodes across both trees is similar and can be represented by the single variable n, the runtime simplifies to O(n).

Space Complexity

O(N) – The primary auxiliary space usage comes from transforming the first tree into a searchable collection, as stated in step 1. This collection, likely a hash set or sorted array, will store nodes from the first tree. In the worst case, the first tree may contain all N nodes, leading to an auxiliary space of O(N) for this collection. The recursive calls implicitly made while visiting nodes in the second tree (step 2) contribute to the call stack, potentially reaching a depth proportional to the height of the second tree, which can also be O(N) in the worst case (skewed tree). Therefore, the overall auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Both BSTs are null	Return false immediately, as no sum can be found.
One BST is null, the other is not	Return false immediately, as we need nodes from both trees.
One or both BSTs contain duplicate values.	The in-order traversal and lookup in the other BST will still work correctly because we are looking for existence of a target value.
Target value is very large (potential overflow during sum calculation)	Use a long data type or appropriate overflow checks to handle potentially large target values.
No pair of nodes sums to the target value	The algorithm should complete the search and return false after exhausting all possibilities.
The BSTs are highly unbalanced, resulting in worst-case traversal time.	Consider balancing BSTs to guarantee O(n) traversal if modifications are allowed, or accept O(n*h) time complexity where h is the height.
Extremely large BSTs that might exceed memory limits when converting to a sorted array.	Use an iterative in-order traversal with a stack to avoid creating large arrays and reduce memory usage.
BSTs contain negative numbers and zero.	The in-order traversal and subsequent target value search in the second BST handles negative numbers and zero correctly.

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 are the possible ranges for node values in the BSTs? Could they be negative, zero, or very large?
Could either of the BSTs be empty or contain only a single node?
If there are multiple pairs across the two BSTs that sum to the target, should I return `true` as soon as I find one, or do I need to find all possible pairs (and if so, how should I return them)?
Are the BSTs guaranteed to be valid BSTs, or do I need to perform validation as part of my solution?
Is there a specific memory constraint I should be aware of, considering I might need to store nodes during traversal?

Brute Force Solution

Approach

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

Take each number from the first tree, one at a time.
For each of those numbers, go through every single number in the second tree.
For each pair of numbers (one from the first tree and one from the second tree), add them together.
See if the sum of the pair is equal to the target value that we are looking for.
If we find a pair that adds up to the target, we have found our answer. We can stop looking.
If we go through every possible pair and don't find a sum that equals the target, then no such pair exists in the two trees.

Code Implementation

def two_sum_bsts_brute_force(root_one, root_two, target_value):
    # Convert BST one to a list
    first_tree_values = []
    def inorder_traversal_one(node):
        if node:
            inorder_traversal_one(node.left)
            first_tree_values.append(node.val)
            inorder_traversal_one(node.right)

    inorder_traversal_one(root_one)

    # Convert BST two to a list
    second_tree_values = []
    def inorder_traversal_two(node):
        if node:
            inorder_traversal_two(node.left)
            second_tree_values.append(node.val)
            inorder_traversal_two(node.right)

    inorder_traversal_two(root_two)

    # Iterate through all possible pairs
    for first_tree_value in first_tree_values:
        # Check every node in the second tree.
        for second_tree_value in second_tree_values:

            # We found our match
            if first_tree_value + second_tree_value == target_value:
                return True

    # If no pair sums to the target, return False
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Transform the first tree into a simple collection that lets you quickly check if a number is present.
Visit each number in the second tree, one by one.
For each number you find in the second tree, calculate what other number would be needed to reach the target sum.
Check if that 'needed' number is in the collection you created from the first tree.
If you find the 'needed' number, you've found your pair, and you're done!
If you go through all the numbers in the second tree and never find the 'needed' number in the first tree's collection, then no such pair exists.

Code Implementation

def find_target_in_two_bsts(root1, root2, target_value):

    # Convert the first BST into a set for fast lookups.
    tree1_values = set()
    def inorder_traversal_tree1(node):
        if node:
            inorder_traversal_tree1(node.left)
            tree1_values.add(node.val)
            inorder_traversal_tree1(node.right)
    inorder_traversal_tree1(root1)

    def inorder_traversal_tree2(node):
        if node:
            # Explore the left subtree
            inorder_traversal_tree2(node.left)

            # Calculate the complement needed from the first tree.
            complement = target_value - node.val

            # Check if the complement exists in the set from tree1.
            if complement in tree1_values:
                return True

            # Explore the right subtree
            if inorder_traversal_tree2(node.right):
                return True

        return False

    # Initiate the search on the second tree, given the set of the first tree
    return inorder_traversal_tree2(root2)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Both BSTs are null	Return false immediately, as no sum can be found.
One BST is null, the other is not	Return false immediately, as we need nodes from both trees.
One or both BSTs contain duplicate values.	The in-order traversal and lookup in the other BST will still work correctly because we are looking for existence of a target value.
Target value is very large (potential overflow during sum calculation)	Use a long data type or appropriate overflow checks to handle potentially large target values.
No pair of nodes sums to the target value	The algorithm should complete the search and return false after exhausting all possibilities.
The BSTs are highly unbalanced, resulting in worst-case traversal time.	Consider balancing BSTs to guarantee O(n) traversal if modifications are allowed, or accept O(n*h) time complexity where h is the height.
Extremely large BSTs that might exceed memory limits when converting to a sorted array.	Use an iterative in-order traversal with a stack to avoid creating large arrays and reduce memory usage.
BSTs contain negative numbers and zero.	The in-order traversal and subsequent target value search in the second BST handles negative numbers and zero correctly.