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

# Two Sum IV - Input is a BST

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

## Analysis

<https://leetcode.com/articles/two-sum-iv/>

**BFS + HashSet**

广度优先搜索，level order traversal：每一个节点遍历时，在hashset里面找是否存在target - currentNode.val，每一层的左右子节点依次放入queue，同时在hashset里面存入当前遍历的节点：

> 1. Remove an element,pp, from the front of thequeuequeue.
> 2. Check if the elementk-pk−palready exists in thesetset. If so, return True.
> 3. Otherwise, add this element,ppto thesetset. Further, add the right and the left child nodes of the current node to the back of thequeuequeue.
> 4. Continue steps 1. to 3. till thequeuequeuebecomes empty.
> 5. Return false if thequeuequeuebecomes empty.

**BST In-order Traversal + Two Pointers**

先in-order遍历BST，输出到一个list，再对这个list用2 sum的方法找target即可，因为list排序过，因此用two pointers很方便。

## Solution

BFS + HashSet - Time: O(n), Space O(n)

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean findTarget(TreeNode root, int k) {
        Queue<TreeNode> queue = new LinkedList();
        Set<Integer> set = new HashSet();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            if (set.contains(k - node.val)) {
                return true;
            }
            set.add(node.val);
        }
        return false;
    }
}
```

BST inorder + Two Pointers

```java
public class Solution {
    public boolean findTarget(TreeNode root, int k) {
        List < Integer > list = new ArrayList();
        inorder(root, list);
        int l = 0, r = list.size() - 1;
        while (l < r) {
            int sum = list.get(l) + list.get(r);
            if (sum == k)
                return true;
            if (sum < k)
                l++;
            else
                r--;
        }
        return false;
    }
    public void inorder(TreeNode root, List < Integer > list) {
        if (root == null)
            return;
        inorder(root.left, list);
        list.add(root.val);
        inorder(root.right, list);
    }
}
```

Recursive + HashSet

```java
public class Solution {
    public boolean findTarget(TreeNode root, int k) {
        Set < Integer > set = new HashSet();
        return find(root, k, set);
    }
    public boolean find(TreeNode root, int k, Set < Integer > set) {
        if (root == null)
            return false;
        if (set.contains(k - root.val))
            return true;
        set.add(root.val);
        return find(root.left, k, set) || find(root.right, k, set);
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/high_frequency/two-sum-iv-input-is-a-bst.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.