653. Two Sum IV - Input is a BST

Problem Statement

Given the root of a binary search tree and an integer k, return true if there exist two elements in the BST such that their sum is equal to k, or false otherwise.

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

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

Intuition

Approach:

Make an inorder and do Two sum

Links

https://leetcode.com/problems/two-sum-iv-input-is-a-bst/description/

Video Links

Approach 1:

Two pointer

C++

class Solution {
public:
    vector<int> arr;
    void inorder(TreeNode *root){
        if(root == nullptr)
            return ;

        inorder(root->left);
        arr.push_back(root->val);
        inorder(root->right);
    }

    bool findTarget(TreeNode* root, int k) {
        inorder(root);
        int low=0, high=arr.size()-1;

        while(low<high){
            int sum = arr[low] + arr[high];
            if(sum == k)
                return true;
            else if(sum > k)
                high--;
            else
                low++;
        }

        return false;
    }
};

Approach 2:

Hash - Two sum

C++

class Solution {
public:
    vector<int> arr;
    void inorder(TreeNode *root){
        if(root == nullptr)
            return ;

        inorder(root->left);
        arr.push_back(root->val);
        inorder(root->right);
    }

    bool findTarget(TreeNode* root, int k) {
        inorder(root);
        unordered_map<int,int> mp;

        for(auto &it: arr){
            if(mp.find(k-it) == mp.end())
                mp[it]++;
            else   
                return true;
        }

        return false;
    }
};

Approach 3:

C++

Approach 4:

C++

Similar Problems