Two Sum IV - Input is a BST

Given the root of a binary search tree and an integer k, return true if there exist two elements in the BST such that their sum is equal to k, or false otherwise.

For example:

• Input: root = [5,3,6,2,4,null,7], k = 9 Output: true
• Input: root = [5,3,6,2,4,null,7], k = 28 Output: false

Constraints:

• The number of nodes in the tree is in the range [1, 10^4]. Validate that the tree meets this size requirement.
• -10^4 <= Node.val <= 10^4. Validate that all nodes meet this value range.
• root is guaranteed to be a valid binary search tree. Confirm that the tree adheres to BST properties.
• -10^5 <= k <= 10^5. Confirm that the target value k is within the specified range.

## Problem Description

Given the root of a binary search tree (BST) and an integer `k`, the task is to determine whether there exist two distinct nodes in the BST such that their values sum up to `k`. Return `true` if such a pair exists; otherwise, return `false`.

## Naive Solution (Brute Force)

One straightforward approach is to traverse the BST and store all node values in a list. Then, iterate through all possible pairs in the list to check if any pair sums up to `k`. This approach has a time complexity of O(n^2) due to the nested loops.

```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def findTarget_brute_force(root: TreeNode, k: int) -> bool:
    values = []

    def inorder_traversal(node):
        if not node:
            return
        inorder_traversal(node.left)
        values.append(node.val)
        inorder_traversal(node.right)

    inorder_traversal(root)

    for i in range(len(values)):
        for j in range(i + 1, len(values)):
            if values[i] + values[j] == k:
                return True

    return False

Optimal Solution (Using a Set)

A more efficient solution involves traversing the BST and using a set to store the visited node values. For each node, check if k - node.val exists in the set. If it does, it means we have found a pair that sums up to k. Otherwise, add the node's value to the set.

def findTarget(root: TreeNode, k: int) -> bool:
    seen = set()

    def inorder_traversal(node):
        if not node:
            return False

        if findTarget(node.left, k):
            return True

        if k - node.val in seen:
            return True

        seen.add(node.val)

        return findTarget(node.right, k)

    return inorder_traversal(root)

Optimal Solution (Inorder Traversal with Two Pointers)

Another optimal solution involves performing an inorder traversal of the BST to get a sorted list of node values. Then, use the two-pointer technique to find if there are two numbers in the list that sum up to k.

def findTarget_two_pointers(root: TreeNode, k: int) -> bool:
    values = []

    def inorder_traversal(node):
        if not node:
            return
        inorder_traversal(node.left)
        values.append(node.val)
        inorder_traversal(node.right)

    inorder_traversal(root)

    left, right = 0, len(values) - 1
    while left < right:
        current_sum = values[left] + values[right]
        if current_sum == k:
            return True
        elif current_sum < k:
            left += 1
        else:
            right -= 1

    return False

Big(O) Runtime Analysis

• Brute Force Solution: O(n^2) because of the nested loops to compare every possible pair.
• Set Solution: O(n) since, in the worst case, we visit each node once.
• Two Pointer Solution: O(n) because the inorder traversal takes O(n) and the two-pointer approach takes O(n).

Big(O) Space Usage Analysis

• Brute Force Solution: O(n) to store all the node values in the list.
• Set Solution: O(n) to store, in the worst case, all the nodes in the set.
• Two Pointer Solution: O(n) to store all the node values in the list.

Edge Cases

• Empty Tree: If the tree is empty (root is None), there can be no pair, so return false.
• Single Node: If the tree contains only one node, it's impossible to find a distinct pair, so return false.
• Duplicate Values: If the tree contains duplicate values, the set solution handles this correctly since it checks for k - node.val in the set before adding the current node's value.
• k Outside Range: If k is too small (smaller than the sum of the two smallest values) or too large (larger than the sum of the two largest values), then return false.