# Determine if two numbers sum to given value in Binary Search Tree problem

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).