Solution Explanation for LeetCode 1214: Two Sum BSTs

This problem asks whether there exist two nodes, one from each of two given Binary Search Trees (BSTs), whose values sum up to a specified target.

Approach: In-order Traversal and Two Pointers

The most efficient approach leverages the property of BSTs: an in-order traversal yields a sorted list of nodes. The solution proceeds in these steps:

1. In-order Traversal: Perform an in-order traversal on both BSTs, root1 and root2. This generates two sorted arrays, nums1 and nums2, containing the values of the nodes in ascending order.

2. Two-Pointer Technique: Employ a two-pointer technique on the sorted arrays.

   • Initialize i = 0 (pointing to the beginning of nums1) and j = nums2.length - 1 (pointing to the end of nums2).
   • Iterate while i < nums1.length and j >= 0.
   • In each iteration, compute the sum x = nums1[i] + nums2[j].
   • If x == target, a pair is found, and true is returned.
   • If x < target, increment i to consider a larger value from nums1.
   • If x > target, decrement j to consider a smaller value from nums2.
   • If the loop completes without finding a pair, return false.

Time and Space Complexity Analysis

• Time Complexity: O(M + N), where M and N are the number of nodes in root1 and root2, respectively. The in-order traversals take O(M) and O(N) time each. The two-pointer approach takes at most O(M + N) time in the worst case.

• Space Complexity: O(M + N). This is due to the space required to store the sorted arrays nums1 and nums2 generated during the in-order traversal. In the worst case, if the trees are skewed, the arrays can hold all the nodes. The recursive stack space for in-order traversal is also considered, which, in the worst case, can be O(M) and O(N) separately. However, it is generally less significant than the space for the arrays.

Code Implementation (Python)

# 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 inorder(root):
            res = []
            stack = []
            while root or stack:
                while root:
                    stack.append(root)
                    root = root.left
                root = stack.pop()
                res.append(root.val)
                root = root.right
            return res
 
        nums1 = inorder(root1)
        nums2 = inorder(root2)
        i, j = 0, len(nums2) - 1
        while i < len(nums1) and j >= 0:
            sum_val = nums1[i] + nums2[j]
            if sum_val == target:
                return True
            elif sum_val < target:
                i += 1
            else:
                j -= 1
        return False

Similar implementations can be easily adapted for Java, C++, Go, and TypeScript using the same algorithm and data structures. The core logic remains consistent across languages. The provided solution in the original response shows examples in these languages.