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