We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Two Sum BSTs

Number: 1150

Difficulty: Medium

Paid? Yes

Companies: Amazon

Problem Description

Given the roots of two binary search trees, root1 and root2, determine if there exists a node from the first tree and a node from the second tree whose values add up exactly to a given integer target.

Key Insights

  • Traverse the first tree to collect all node values.
  • Traverse the second tree to check for each node if the complement (target - current node value) exists in the first tree’s values.
  • Using a hash set for the first tree values allows efficient O(1) lookups.
  • The BST property is not essential for the hash set solution, but can be exploited if using iterator techniques for a two-pointer approach.

Space and Time Complexity

Time Complexity: O(n + m) where n and m are the number of nodes in the first and second trees respectively. Space Complexity: O(n) for storing the node values from the first tree (in worst-case scenario).

Solution

We perform a DFS (or any tree traversal) on the first BST to collect all its values in a hash set. Then, we traverse the second BST and for each node, we calculate the complement (target - node value) and check whether this complement exists in the hash set. If we find such a pair, we return true. If no such pair exists after traversing the second tree completely, we return false.

This approach is straightforward and leverages extra space (the set) for constant time lookups, yielding an overall linear time complexity relative to the number of nodes.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def twoSumBSTs(root1: TreeNode, root2: TreeNode, target: int) -> bool:
    # Create a set to store values from the first BST.
    values_set = set()
    
    # Helper function to perform DFS and add node values to the set.
    def dfs_collect(node):
        if not node:
            return
        values_set.add(node.val)  # Add current node value
        dfs_collect(node.left)    # Traverse left subtree
        dfs_collect(node.right)   # Traverse right subtree
    
    # Collect all values from first tree.
    dfs_collect(root1)
    
    # Helper function to traverse second tree and check for complement.
    def dfs_check(node):
        if not node:
            return False
        # If the complement exists in the first tree values, return True.
        if target - node.val in values_set:
            return True
        # Recursively check left and right children.
        return dfs_check(node.left) or dfs_check(node.right)
    
    # Check the second tree.
    return dfs_check(root2)

# Example usage:
# Construct trees and call twoSumBSTs as needed.
← Back to All Questions