Problem Description

You are given two binary search trees (BSTs), root1 and root2, and an integer target. Your task is to determine if there exists a pair of nodes, one from each tree, such that the sum of their values equals target.

• You must pick one node from root1 and one node from root2.
• Node values should not be reused; each node can only be used once per pair.
• Return True if such a pair exists, otherwise return False.

The trees are guaranteed to be valid BSTs. The problem is a variant of the classic "Two Sum" but applied across two different trees.

Thought Process

At first glance, the problem looks similar to the "Two Sum" problem, but instead of working with a single array, we have two trees. The brute-force approach would be to compare every node in the first tree with every node in the second tree, checking if their sum equals target. However, since each tree could have many nodes, this approach would be inefficient.

To optimize, we should leverage the properties of BSTs. Since BSTs allow for efficient searching, we can improve our solution by searching for the complement value (target - x) of each node x in root1 within root2. This reduces unnecessary comparisons and takes advantage of BST search efficiency.

Alternatively, we could flatten one or both BSTs into sorted lists and use a two-pointer approach, but searching directly in the BST is often more space-efficient.

Solution Approach

Here’s a step-by-step breakdown of the optimized solution:

1. Traverse the first BST:
   • Use any traversal method (in-order, pre-order, etc.) to visit each node in root1.
2. For each node in root1, search for its complement in root2:
   • The complement is target - node1.val.
   • Use BST search (O(log n) in average case) to look for this value in root2.
3. If a matching pair is found, return True:
   • As soon as you find such a pair, you can terminate early.
4. If no pair is found after traversing all nodes, return False:

Why use this approach?

• BST search is efficient, so searching for complements is much faster than brute-force.
• This approach avoids extra space (unlike building large lists or sets), unless you choose to use a hash set for even faster lookups.

• You could flatten both BSTs into sorted lists and use the two-pointer technique. This is also efficient but uses O(N+M) space.

Example Walkthrough

Suppose we have:

• root1: BST with values [2, 1, 4]
• root2: BST with values [1, 0, 3]
• target = 5

1. Traverse root1:
   • First node: 2. Complement = 5 - 2 = 3.
   • Search 3 in root2: Found! (node with value 3 exists in root2).
   • Return True immediately, since we found a valid pair (2 from root1 and 3 from root2).
2. If not found, continue:
   • Next node: 1. Complement = 5 - 1 = 4. 4 is not in root2.
   • Next node: 4. Complement = 5 - 4 = 1. 1 is in root2.
   • Return True (if previous pair was not found).

In this example, the algorithm finds the answer quickly by using BST search rather than checking all possible pairs.

Time and Space Complexity

Brute-force approach:

• Time Complexity: O(N * M), where N and M are the number of nodes in root1 and root2.
• Space Complexity: O(1) (excluding recursion stack space).

• Time Complexity: O(N * log M) on average, since for each node in root1 we search root2 (average BST search is O(log M)). In the worst case (unbalanced BST), search could be O(M), but usually it's much better.
• Space Complexity: O(H), where H is the height of the trees, due to recursion stack for traversals.

• If you store all values from root2 in a set, you get O(N + M) time and O(M) space.

Summary

The "Two Sum BSTs" problem extends the classic two-sum challenge to two binary search trees. By leveraging BST properties, we can efficiently search for complements, avoiding brute-force inefficiency. The solution demonstrates how tree traversal and search can be combined for an elegant, optimized result, making the most of BST structure and minimizing unnecessary computation.

Code Implementation

# 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

class Solution:
    def twoSumBSTs(self, root1: TreeNode, root2: TreeNode, target: int) -> bool:
        def search(root, val):
            if not root:
                return False
            if root.val == val:
                return True
            elif root.val < val:
                return search(root.right, val)
            else:
                return search(root.left, val)
        
        def dfs(node):
            if not node:
                return False
            complement = target - node.val
            if search(root2, complement):
                return True
            return dfs(node.left) or dfs(node.right)
        
        return dfs(root1)
      

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool search(TreeNode* root, int val) {
        if (!root) return false;
        if (root->val == val) return true;
        else if (root->val < val) return search(root->right, val);
        else return search(root->left, val);
    }
    
    bool dfs(TreeNode* node, TreeNode* root2, int target) {
        if (!node) return false;
        int complement = target - node->val;
        if (search(root2, complement)) return true;
        return dfs(node->left, root2, target) || dfs(node->right, root2, target);
    }
    
    bool twoSumBSTs(TreeNode* root1, TreeNode* root2, int target) {
        return dfs(root1, root2, target);
    }
};
      

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean twoSumBSTs(TreeNode root1, TreeNode root2, int target) {
        return dfs(root1, root2, target);
    }
    
    private boolean dfs(TreeNode node, TreeNode root2, int target) {
        if (node == null) return false;
        int complement = target - node.val;
        if (search(root2, complement)) return true;
        return dfs(node.left, root2, target) || dfs(node.right, root2, target);
    }
    
    private boolean search(TreeNode root, int val) {
        if (root == null) return false;
        if (root.val == val) return true;
        else if (root.val < val) return search(root.right, val);
        else return search(root.left, val);
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @param {number} target
 * @return {boolean}
 */
var twoSumBSTs = function(root1, root2, target) {
    function search(node, val) {
        if (!node) return false;
        if (node.val === val) return true;
        else if (node.val < val) return search(node.right, val);
        else return search(node.left, val);
    }
    function dfs(node) {
        if (!node) return false;
        let complement = target - node.val;
        if (search(root2, complement)) return true;
        return dfs(node.left) || dfs(node.right);
    }
    return dfs(root1);
};