# 0653. Two Sum IV - Input is a BST

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Two Sum IV - Input is a BST](https://leetcode.com/problems/two-sum-iv-input-is-a-bst/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0653-two-sum-iv-input-is-a-bst)

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*.
{% endtab %}

{% tab title="✍🏻 Constraints & Example" %}
**Constraints:**

* The number of nodes in the tree is in the range `[1, 10^4]`.
* `-10^4 <= Node.val <= 10^4`
* `root` is guaranteed to be a **valid** binary search tree.
* `-10^5 <= k <= 10^5`
  {% endtab %}
  {% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
Using **"Stack" to traverse** BST and using **"Set" to record** each node value.
{% endhint %}
{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="🤖 Python3" %}

```python
class Solution:
    def findTarget(self, root: TreeNode, k: int) -> bool:
        
        # ==================================================
        #  Binary Search Tree + Stack                      =
        # ==================================================
        # time  : O(n)
        # space : O(n)
        
        stack = [root]
        values = set()
        
        while stack:
            node = stack.pop()
            if k - node.val in values: return True
            values.add(node.val)
            
            if node.left: stack.append(node.left)
            if node.right: stack.append(node.right)
        
        return False
```

{% endtab %}

{% tab title=" 🤖 Java" %}

```java
class Solution {
    /**  
     * @time  : O(n)
     * @space : O(n)
     */
    
    public boolean findTarget(TreeNode root, int k) {
        HashSet<Integer> values = new HashSet<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if(values.contains(k - node.val)) return true;
            values.add(node.val);
            
            if(node.left != null) stack.push(node.left);
            if(node.right != null) stack.push(node.right);
        }
        
        return false;
    }
}
```

{% endtab %}
{% endtabs %}