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.

&nbsp;
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


&nbsp;
Constraints:


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


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        def inorder(root,l):
            if root:
                inorder(root.left,l)
                l.append(root.val)
                inorder(root.right,l)
        l = []
        inorder(root,l)
        left,right=0,len(l)-1
        while left!=right:
            sum = l[left] + l[right]
            if sum > k :
                right -=1
            elif sum <k:
                left +=1
            else:
                return 1
        return 0
class Solution {
    Set<Integer> set = new HashSet<>();
    public boolean findTarget(TreeNode root, int k) {
        if(root == null){
            return false;
        }
        if(set.contains(k-root.val)){
            return true;
        }
        set.add(root.val);
        return findTarget(root.left,k) || findTarget(root.right,k);
    }
}
class Solution {
public:
    int countNodes(TreeNode *root) {
        if (root == NULL) {
            return 0;
        }
        return countNodes(root->left) + countNodes(root->right) + 1;
    }

    bool findTarget(TreeNode* root, int k) {
        int totalCount = countNodes(root);
        int count = 0;
        stack<TreeNode*> inorder;
        stack<TreeNode*> revInorder;

        TreeNode* currNode = root;
        while(currNode != NULL){
            inorder.push(currNode); //Store all elements in left of tree
            currNode = currNode->left;
        }

        currNode = root;
        while(currNode != NULL){
            revInorder.push(currNode); //Store all elements in right of tree
            currNode = currNode->right;
        }

        while(count < totalCount-1){
            TreeNode* inordertop = inorder.top();
            TreeNode* revinordertop = revInorder.top();
            if(inordertop->val + revinordertop->val == k){ // If inordertop + revinordertop is equal to k, we have found a pair, so return true
                return true;
            }
            else if(inordertop->val + revinordertop->val > k){ //If they are greater than k, we have to found a value
            //which is just smaller than revinordertop, which means we have to find predecessor of revinordertop, as
            //we have to reduce the sum to make it equal to k
                TreeNode* currtop = revinordertop;
                count++;
                revInorder.pop();
                if(currtop->left){
                    currtop = currtop->left;
                    while(currtop){
                        revInorder.push(currtop);
                        currtop = currtop->right;
                    }
                }
            }
            else{
            //If they are smaller than k, we have to found a value which is just larger than inordertop, which means
            //we have to find successor of revinordertop, as we have to increase the sum to make it equal to k
                TreeNode* currtop = inordertop;
                count++;
                inorder.pop();
                if(currtop->right){
                    currtop = currtop->right;
                    while(currtop){
                        inorder.push(currtop);
                        currtop = currtop->left;
                    }
                }
            }
        }
        return false;
    }
};
var findTarget = function(root, k) {

    const set = new Set();

    const search = (root, k) => {
        if (!root) return false;
        if (set.has(k - root.val)) return true;
        set.add(root.val);
        return search(root.left, k) || search(root.right, k);
    }

    return search(root,k);
};
Two Sum IV - Input is a BST