algoadvance

Given the root of a Binary Search Tree (BST) and an integer target, return true if there exist two elements in the BST such that their sum is equal to the given target, or false otherwise.

Example:

Input: root = [5,3,6,2,4,null,7], target = 9
Output: true
Explanation: 3 + 6 = 9

Input: root = [5,3,6,2,4,null,7], target = 28
Output: false
Explanation: There are no two nodes in the BST that add up to 28.

Clarifying Questions:

  1. Can the BST have duplicate values?
  2. What is the range of values for the elements of the BST and the target?
  3. Is there any constraint on the tree size?

Strategy

  1. BST Properties: Use the BST properties where the left child is less than the parent and the right child is greater than the parent to devise an efficient search strategy.
  2. Inorder Traversal: Perform an inorder traversal of the BST to convert it into a sorted array.
  3. Two Pointer Technique: Use the two-pointer method on the sorted array to find the pair that sums up to the target.

Code

# 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

def findTarget(root: TreeNode, target: int) -> bool:
    # Helper function for inorder traversal
    def inorder(node: TreeNode) -> list:
        if not node:
            return []
        return inorder(node.left) + [node.val] + inorder(node.right)
    
    # Convert BST to a sorted list using inorder traversal
    values = inorder(root)
    
    # Use two pointers to find the target sum in the sorted list
    left, right = 0, len(values) - 1

    while left < right:
        current_sum = values[left] + values[right]
        if current_sum == target:
            return True
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    
    return False

Time Complexity

  1. Inorder Traversal: O(n)
  2. Two Pointer Search: O(n)

Overall time complexity is O(n) where n is the number of nodes in the BST.

Space Complexity

  1. Space used by the recursion stack in the inorder traversal: O(h) where h is the height of the tree.
  2. Space used to store the inorder traversal list: O(n)

Thus, the overall space complexity is O(n).

Try our interview co-pilot at AlgoAdvance.com