> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/tree/1214.-two-sum-bsts.md).

# 1214. Two Sum BSTs

Given two binary search trees, 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:**

![](https://assets.leetcode.com/uploads/2019/05/31/1368_1_a2.png)![](https://assets.leetcode.com/uploads/2019/05/31/1368_1_b.png)

```
Input: root1 = [2,1,4], root2 = [1,0,3], target = 5
Output: true
Explanation: 2 and 3 sum up to 5.
```

**Example 2:**

![](https://assets.leetcode.com/uploads/2019/05/31/1368_2_a.png)![](https://assets.leetcode.com/uploads/2019/05/31/1368_2_b.png)

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

**Constraints:**

* Each tree has at most `5000` nodes.
* `-10^9 <= target, node.val <= 10^9`

```cpp
// Iteration with Two Stacks
bool twoSumBSTs(TreeNode* root1, TreeNode* root2, int target) { // time: O(m + n); space: O(m + n)
    // Use inorder traversal to traverse from the smallerst node in BST1 and the largest node in BST2
    stack<TreeNode*> st1, st2;
    TreeNode *t1 = root1, *t2 = root2;
    while (true) {
        // BST1 inorder successor
        while (t1) {
            st1.push(t1);
            t1 = t1->left;
        }
        // BST2 inorder predecessor
        while (t2) {
            st2.push(t2);
            t2 = t2->right;
        }
        if (st1.empty() || st2.empty()) break;
        t1 = st1.top();
        t2 = st2.top();
        int sum = t1->val + t2->val;
        if (sum == target) return true;
        else if (sum < target) {
            st1.pop();
            t1 = t1->right;
            t2 = nullptr;
        } else {
            st2.pop();
            t2 = t2->left;
            t1 = nullptr;
        }
    }
    return false;
}
```

```cpp
// Recursion
bool helper(TreeNode* node, int k) {
    if (!node) return false;
    if (node->val == k) return true;
    else if (node->val < k) return helper(node->right, k);
    else return helper(node->left, k);
}
bool twoSumBSTs(TreeNode* root1, TreeNode* root2, int target) {
    if (!root1) return false;
    return helper(root2, target - root1->val) 
        || twoSumBSTs(root1->left, root2, target) 
        || twoSumBSTs(root1->right, root2, target);
}
```