1150. Two Sum BSTs

• Difficulty: Medium

• Topics: Binary Search Tree

• Similar Questions:

  • Two Sum IV - Input is a BST

Problem:

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

Solutions:

/**
 * 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 twoSumBSTs(TreeNode* root1, TreeNode* root2, int target) {
        unordered_set<int> visited;
        dfs(root1, target, visited, true);
        return dfs(root2, target, visited, false);
    }

private:
    bool dfs(TreeNode* root, int target, unordered_set<int>& visited, bool populate) {
        if (root == nullptr)    return false;
        if (populate) {
            visited.insert(root->val);
        } else {
            if (visited.count(target - root->val))  return true;
        }

        return dfs(root->left, target, visited, populate) || dfs(root->right, target, visited, populate);
    }

};