Saw this problem in LeetCode.

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.

Python based 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 find(self, root: TreeNode, k: int, alreadyUsed: TreeNode) -> bool:
if root.val == k and root is not alreadyUsed:
return True
if k < root.val and root.left is not None:
return self.find(root.left, k, alreadyUsed)
if k >= root.val and root.right is not None:
return self.find(root.right, k, alreadyUsed)
return False
def findInPart(self, part: TreeNode, root : TreeNode, k: int) -> bool:
toFind = k - part.val;
if self.find(root, toFind, part):
return True
if part.left is not None and self.findInPart(part.left, root, k):
return True
if part.right is not None and self.findInPart(part.right, root, k):
return True
return False
def findTarget(self, root: TreeNode, k: int) -> bool:
toFind = k - root.val;
if self.find(root, toFind, root):
return True
if root.left is not None and self.findInPart(root.left, root, k):
return True
if root.right is not None and self.findInPart(root.right, root, k):
return True
return False
```

This is a very simple solution.

The solution given here has time complexity of O(n Log n) for average case assuming the binary search tree is somewhat balanced. Space complexity is O(1) as I don’t allocate any new data structure.

By keeping track of the the elements you have already seen in a Set as you are doing the traversal you can improve the time complexity here to O(n) with space complexity of O(n).