653

653. Two Sum IV - Input is a BST (Easy)

Given the root of a Binary Search Tree and a target number k, return true if there exist two elements in the BST such that their sum is equal to the given target.

 

Example 1:

Input: root = [5,3,6,2,4,null,7], k = 9
Output: true

Example 2:

Input: root = [5,3,6,2,4,null,7], k = 28
Output: false

Example 3:

Input: root = [2,1,3], k = 4
Output: true

Example 4:

Input: root = [2,1,3], k = 1
Output: false

Example 5:

Input: root = [2,1,3], k = 3
Output: true

 

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• -104 <= Node.val <= 104
• root is guaranteed to be a valid binary search tree.
• -105 <= k <= 105

Companies:
Microsoft

Related Topics:
Hash Table, Two Pointers, Tree, Depth-First Search, Breadth-First Search, Binary Search Tree, Binary Tree

Similar Questions:

• Two Sum (Easy)
• Two Sum II - Input array is sorted (Easy)
• Two Sum III - Data structure design (Easy)
• Two Sum BSTs (Medium)

Solution 1.

For each node with value num (2 * num != target), find if target - num is in the BST.

This solution is good when the BST is balanced, i.e. H = logN. But when the BST is skewed, this solution degrades to O(N^2) time complexity and O(N) space.

// OJ: https://leetcode.com/problems/two-sum-iv-input-is-a-bst/solution/
// Author: github.com/lzl124631x
// Time: O(NH)
// Space: O(H)
class Solution {
    bool dfs(TreeNode *root, int k, int mn = INT_MIN, int mx = INT_MAX) {
        if (!root || root->val <= mn || root->val >= mx) return false;
        if (root->val == k) return true;
        return root->val < k ? dfs(root->right, k, root->val, mx) : dfs(root->left, k, mn, root->val);
    }
    bool find(TreeNode *root, int k, TreeNode *from) {
        if (!root) return false;
        if (2 * root->val != k && dfs(from, k - root->val)) return true;
        return find(root->left, k, from) || find(root->right, k, from);
    }
public:
    bool findTarget(TreeNode* root, int k) {
        return find(root, k, root);
    }
};

Solution 2. Preorder Traversal + Unordered Set

This solution doesn't leverage the nature of the BST. It's a two sum solution using an unordered_set.

// OJ: https://leetcode.com/problems/two-sum-iv-input-is-a-bst/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
    unordered_set<int> s;
public:
    bool findTarget(TreeNode* root, int k) {
        if (!root) return false;
        if (s.count(k - root->val)) return true;
        s.insert(root->val);
        return findTarget(root->left, k) || findTarget(root->right, k);
    }
};

Solution 2. Inorder Traversal + Two Pointers

// OJ: https://leetcode.com/problems/two-sum-iv-input-is-a-bst/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
private:
    vector<int> v;
    void inorder(TreeNode *root) {
        if (!root) return;
        inorder(root->left);
        v.push_back(root->val);
        inorder(root->right);
    }
public:
    bool findTarget(TreeNode* root, int k) {
        inorder(root);
        int i = 0, j = v.size() - 1;
        while (i < j) {
            int sum = v[i] + v[j];
            if (sum == k) return true;
            if (sum > k) --j;
            else ++i;
        }
        return false;
    }
};