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:

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

Example 2:

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

// 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;
}

// 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);
}