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

Example 1:

Input: 5 /
3 6 / \
2 4 7

Target = 9

Output: True

Example 2:

Input: 5 /
3 6 / \
2 4 7

Target = 28

Output: False

core idea is tree traversal with hashset approach 1 recursion +HashSet timeO(N) space O(N+H) size of set and recursion height

# Definition for a binary tree node.
# time O(N) space O(N)
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
<<<<<<< HEAD
<<<<<<< HEAD
"""
main idea: use set to record value that has been visited/ value that hope to encounter
"""
    def findTarget(self, root: TreeNode, k: int) -> bool:
        s = set()
        def find(node):
    def findTarget(self, root: TreeNode, k: int) -> bool:
        s = set()
        def find(node,k,Set):

    def findTarget(self, root: TreeNode, k: int) -> bool:
        s = set()
        def find(node,k,Set):
            if not node:
                return False
            if k-node.val in s:
                return True
            s.add(node.val)
            return find(node.left) or find(node.right)

        return find(root)

approach 2 BFS (queue)+ HashSet time O(n) space O(N+N): size of set and queue length

# 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: TreeNode, k: int) -> bool:
        #1. check if root empty
        if not root:
            return False
        s = set()
        queue = [root]
        for node in queue:
            if k-node.val in s:
                return True
            s.add(node.val)
            if node.left: 
                queue.append(node.left)
            if node.right: 
                queue.append(node.right)
        return False