Two Sum IV - Input is a BST

Problem Statement

The problem requires you to find whether there are two distinct nodes in a given binary search tree (BST) such that their values sum up to a specific target integer k. If such a pair exists, the function should return true, otherwise false. A BST is a tree structure where each node has up to two children, and it follows the properties where every node in the left subtree of a node has a value less than or equal to the node’s value, and every node in the right subtree has a value greater than the node’s value. This natural order property influences how we can efficiently search and manage data within the tree.

Examples

Example 1

Input:

root = [5,3,6,2,4,null,7], k = 9

Output:

true

Example 2

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, 104].
• -104 <= Node.val <= 104
• root is guaranteed to be a valid binary search tree.
• -105 <= k <= 105

Approach and Intuition

To solve this problem efficiently given the constraints and property of BST, we can consider the following approach:

1. Since the elements are arranged in a specific order (due to the BST properties), we can efficiently search for a required compliment of a current node value that sums to k.
2. A practical and simple approach is to use an auxiliary data structure, such as a set, to keep track of the visited nodes while traversing the tree. This allows checking in constant time whether the complement k - current_node_value exists in the set.
3. Alternatively, given the sorted nature of BST when In-Order traversed, another effective way is to use two pointers approach similar to the two-sum problem on a sorted array:
   • Convert the BST to a sorted list by in-order traversal.
   • Use two pointers, one starting from the beginning (left_pointer) and the other from the end (right_pointer) of the sorted list.
   • Based on the sum of the values at these two pointers, decide to move the left_pointer to the right or the right_pointer to the left.
4. The search operation can be stopped as soon as the two pointers cross each other. If a pair is found before the pointers cross, return true, otherwise false.

The first approach offers the ability to maintain the traversal without needing extra space proportional to the number of elements in the BST (outside the set used for look-up). The second approach, while requiring linear space to store the sorted list, offers straightforward and intuitive operations based on the properties of a sorted sequence. Each approach adheres to the constraints provided and leverages the BST properties to ensure efficient performance.

Solutions

public class Solution {
    public boolean checkIfSumExists(TreeNode node, int target) {
        List<Integer> elements = new ArrayList<>();
        traverseInOrder(node, elements);
        int left = 0, right = elements.size() - 1;
        while (left < right) {
            int currentSum = elements.get(left) + elements.get(right);
            if (currentSum == target)
                return true;
            if (currentSum < target)
                left++;
            else
                right--;
        }
        return false;
    }
    public void traverseInOrder(TreeNode node, List<Integer> elements) {
        if (node == null)
            return;
        traverseInOrder(node.left, elements);
        elements.add(node.val);
        traverseInOrder(node.right, elements);
    }
}