> For the complete documentation index, see [llms.txt](https://nataliekung.gitbook.io/ladder_code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nataliekung.gitbook.io/ladder_code/facebook/two-sum-iv-input-is-a-bstbfs+set.md).

# Two Sum IV - Input is a BST(bfs+set)

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
```

分析

two sum。一个queue存元素，一个set存值。bfs 每次检查k-root.val是否在set里

```
class Solution:
       def findTarget(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: bool
        """
        if not root:
            return False
        s = set()
        q = collections.deque([root])
        while q:
            n = q.popleft()
            if n:
                if k - n.val in s:
                    return True
                s.add(n.val)
                q.append(n.left)
                q.append(n.right)

        return False
```