## Introduction

Binary Search Trees (BSTs) are a widely-used data structure in computer science. They allow efficient storage, retrieval, and deletion of data in a sorted manner. In this article, we are going to delve into solving the “Two Sum IV – Input is a BST” problem from Leetcode. This problem combines the concept of the Two Sum problem with the properties of a Binary Search Tree. We will explore the problem in detail, discuss various approaches for solving it, and provide Python code for each solution.

## Problem Statement

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:

Input: `root = [5,3,6,2,4,null,7], k = 9`

Output: `true`

Explanation: The BST is:

```
5
/ \
3 6
/ \ \
2 4 7
```

5 + 4 = 9, so return `true`

.

### Note:

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

## Solution

### 1. In-Order Traversal and Two Pointers

One way to approach this problem is to use an in-order traversal to retrieve the elements of the BST in ascending order. Once we have the elements in sorted order, we can use the two-pointer technique to check for two elements whose sum equals the target `k`

.

- Perform an in-order traversal to get the elements in ascending order.
- Use two pointers, one at the beginning and one at the end of the array.
- Move the pointers inward until they meet, checking if the sum of the elements they point to is equal to
`k`

.

```
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def find_target(self, root, k):
def in_order_traversal(node):
if not node:
return []
return in_order_traversal(node.left) + [node.val] + in_order_traversal(node.right)
elements = in_order_traversal(root)
left, right = 0, len(elements) - 1
while left < right:
current_sum = elements[left] + elements[right]
if current_sum == k:
return True
elif current_sum < k:
left += 1
else:
right -= 1
return False
```

#### Time Complexity:

- O(n), where n is the number of nodes in the BST.

#### Space Complexity:

- O(n), due to storing the elements of the BST in an array.

### 2. Using a Hash Set

We can solve this problem in a single pass through the BST using a hash set. During the traversal, for each node, we check if the difference between the target value `k`

and the current node’s value is in the hash set. If it is, we have found two elements that add up to `k`

.

- Perform any tree traversal (in-order, pre-order, post-order).
- For each node, check if
`k - node.val`

is in the hash set. - If not, add
`node.val`

to the hash set.

```
class Solution:
def find_target(self, root, k):
def dfs(node, seen):
if not node:
return False
complement = k - node.val
if complement in seen:
return True
seen.add(node.val)
return dfs(node.left, seen) or dfs(node.right, seen)
return dfs(root, set())
```

#### Time Complexity:

- O(n), where n is the number of nodes in the BST.

#### Space Complexity:

- O(n), due to storing the elements in a hash set.

## Conclusion

In this article, we explored the “Two Sum IV – Input is a BST” problem on Leetcode and discussed two different approaches in Python: In-Order Traversal with Two Pointers and Hash Set. While both solutions have the same time and space complexity, the Hash Set approach is arguably more concise and requires only a single pass through the BST.