# LeetCode 653. Two Sum IV – Input is a BST

## Description

https://leetcode.com/problems/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.

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

Example 3:

```Input: root = [2,1,3], k = 4
Output: true
```

Example 4:

```Input: root = [2,1,3], k = 1
Output: false
```

Example 5:

```Input: root = [2,1,3], k = 3
Output: true
```

Constraints:

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

## Explanation

Inorder traverse the binaray search tree to build a list of node values in ascending order. Then use two pointers technique to find whether there are two elements adding up together equal to k.

## Python Solution

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

values = []
self.inorder_traverse(root, values)

left = 0
right = len(values) - 1

while left < right:
if values[left] + values[right] < k:
left += 1
elif values[left] + values[right] > k:
right -= 1
else:
return True

return False

def inorder_traverse(self, root, results):
if not root:
return

self.inorder_traverse(root.left, results)
results.append(root.val)
self.inorder_traverse(root.right, results)

``````
• Time Complexity: O(N).
• Space Complexity: O(N).