Solutions

1. Brute Force

Intuition

The simplest approach is to collect all values from both trees and check every possible pair. If any pair sums to the target, we have found our answer.

Algorithm

Traverse the first tree and store all node values in a list.
Traverse the second tree and store all node values in another list.
For each value a in the first list and each value b in the second list, check if a + b == target.
Return true if a valid pair is found, false otherwise.

class Solution:
    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:
        def dfs(curr_node, node_list):
            if not curr_node:
                return
            node_list.append(curr_node.val)
            dfs(curr_node.left, node_list)
            dfs(curr_node.right, node_list)
        
        node_list1, node_list2 = [], []
        dfs(root1, node_list1)
        dfs(root2, node_list2)
        
        for a in node_list1:
            for b in node_list2:
                if a + b == target:
                    return True
        return False

Time & Space Complexity

Time complexity: $O(m \cdot n)$
Space complexity: $O(m+n)$

Where $m$ and $n$ are the number of nodes in the two trees.

2. Binary Search

Intuition

Since the second tree is a BST, we can leverage its sorted structure. For each node in the first tree, we compute the complement (target - node.val) and use binary search to check if that complement exists in the second tree.

Algorithm

Traverse the first BST using dfs.
For each node with value v, compute complement = target - v.
Perform binary search in the second BST to find the complement:
- If current value equals complement, return true.
- If current value is greater, search left.
- Otherwise, search right.
If no pair is found after checking all nodes, return false.

class Solution:
    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:
        def binarySearch(root2, target2):
            if not root2:
                return False
            if root2.val == target2:
                return True
            elif root2.val > target2:
                return binarySearch(root2.left, target2)
            else:
                return binarySearch(root2.right, target2)

        def dfs(root, target):
            if not root:
                return False
            if binarySearch(root2, target - root.val):
                return True
            return dfs(root.left, target) or dfs(root.right, target)

        return dfs(root1, target)

Time & Space Complexity

Time complexity: $O(m \cdot \log n)$
Space complexity: $O(\log m + \log n)$

Where $m$ and $n$ are the number of nodes in the two trees.

3. Hash Set

Intuition

We can trade space for time by storing all values from one tree in a hash set. Then for each value in the other tree, we check if the complement exists in the set in O(1) time.

Algorithm

Traverse the first tree and add all values to a hash set.
Traverse the second tree and add all values to another hash set.
For each value in the first set, check if target - value exists in the second set.
Return true if found, false otherwise.

class Solution:
    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:
        def dfs(curr_node, node_set):
            if not curr_node:
                return
            dfs(curr_node.left, node_set)
            node_set.add(curr_node.val)
            dfs(curr_node.right, node_set)
        
        node_set1, node_set2 = set(), set()
        dfs(root1, node_set1)
        dfs(root2, node_set2)
        
        for value1 in node_set1:
            if target - value1 in node_set2:
                return True
        return False

Time & Space Complexity

Time complexity: $O(m + n)$
Space complexity: $O(m + n)$

Where $m$ and $n$ are the number of nodes in the two trees.

4. Two Pointers

Intuition

An inorder traversal of a BST produces a sorted list. If we have sorted lists from both trees, we can use the classic two-pointer technique: one pointer starts at the beginning of the first list (smallest), and another starts at the end of the second list (largest). We adjust pointers based on whether the current sum is too small or too large.

Algorithm

Perform inorder traversal on both trees to get two sorted lists.
Initialize pointer1 = 0 (start of first list) and pointer2 = len(list2) - 1 (end of second list).
While both pointers are valid:
- If sum equals target, return true.
- If sum is less than target, increment pointer1.
- If sum is greater than target, decrement pointer2.
Return false if no pair is found.

class Solution:
    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:
        def dfs(curr_node, node_list):
            if not curr_node:
                return
            dfs(curr_node.left, node_list)
            node_list.append(curr_node.val)
            dfs(curr_node.right, node_list)
        
        node_list1, node_list2 = [], []
        dfs(root1, node_list1)
        dfs(root2, node_list2)
        
        pointer1 = 0
        pointer2 = len(node_list2) - 1
        while pointer1 < len(node_list1) and pointer2 >= 0:
            if node_list1[pointer1] + node_list2[pointer2] == target:
                return True
            elif node_list1[pointer1] + node_list2[pointer2] < target:
                pointer1 += 1
            else:
                pointer2 -= 1
        return False

Time & Space Complexity

Time complexity: $O(m + n)$
Space complexity: $O(m + n)$

Where $m$ and $n$ are the number of nodes in the two trees.

5. Morris Traversal

Intuition

The two-pointer approach requires O(m + n) space to store the sorted lists. Morris traversal lets us iterate through a BST in sorted order using O(1) extra space by temporarily modifying tree pointers. We use forward Morris traversal on one tree and reverse Morris traversal on the other to simulate the two-pointer technique without extra space.

Algorithm

Create a forward Morris iterator for the first tree (yields values in ascending order).
Create a reverse Morris iterator for the second tree (yields values in descending order).
Get the first value from each iterator.
While both values are valid:
- If sum equals target, return true.
- If sum is less than target, advance the forward iterator.
- If sum is greater than target, advance the reverse iterator.
Return false if no pair is found.

class Solution:
    def twoSumBSTs(self, root1: Optional[TreeNode], root2: Optional[TreeNode], target: int) -> bool:
        def morris_traversal(root):
            current = root
            while current:
                if not current.left:
                    yield current.val
                    current = current.right
                else:
                    pre = current.left
                    while pre.right and pre.right != current:
                        pre = pre.right
                    if not pre.right:
                        pre.right = current
                        current = current.left
                    else:
                        pre.right = None
                        yield current.val
                        current = current.right

        def reversed_morris_traversal(root):
            current = root
            while current:
                if not current.right:
                    yield current.val
                    current = current.left
                else:
                    pre = current.right
                    while pre.left and pre.left != current:
                        pre = pre.left
                    if not pre.left:
                        pre.left = current
                        current = current.right
                    else:
                        pre.left = None
                        yield current.val
                        current = current.left
                        
        iterater1 = morris_traversal(root1)
        iterater2 = reversed_morris_traversal(root2)
        value1 = next(iterater1, None)
        value2 = next(iterater2, None)

        while value1 is not None and value2 is not None:
            if value1 + value2 == target:
                return True
            elif value1 + value2 < target:
                value1 = next(iterater1, None)
            else:
                value2 = next(iterater2, None)
        return False

Time & Space Complexity

Time complexity: $O(m + n)$
Space complexity: $O(1)$

Where $m$ and $n$ are the number of nodes in the two trees.

Common Pitfalls

Treating the Trees as Regular Binary Trees

A common mistake is ignoring the BST property and treating both trees as generic binary trees. This leads to inefficient solutions that don't leverage the sorted structure for binary search or two-pointer approaches. Always consider whether the BST ordering can help optimize your search.

Computing the Complement Incorrectly

When searching for a pair that sums to the target, some forget to compute target - value correctly or accidentally search for the wrong value. For example, if target = 9 and the current node has value 4, you need to search for 5 in the other tree, not 9 - 4 = 5 with any other formula.

Modifying Tree Structure with Morris Traversal

Morris traversal temporarily modifies tree pointers to achieve O(1) space. A pitfall is forgetting to restore the original tree structure after traversal or exiting early without cleanup. This can corrupt the tree for subsequent operations or cause infinite loops.