Two Sum IV - Input is a BST

Leetcode 653. 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.

Approach 1: Iterative:

class Solution {
    public boolean findTarget(TreeNode root, int k) {
        return find(root, root, k);
    }

    private boolean find(TreeNode root, TreeNode current, int k) {
        if (current == null) return false;

        int complement = k - current.val;

        // Check if the complement exists in the tree excluding the current node
        if (searchBST(root, current, complement)) return true;

        // Continue to search in the left and right subtrees
        return find(root, current.left, k) || find(root, current.right, k);
    }

    private boolean searchBST(TreeNode root, TreeNode excludeNode, int x) {
        if (root == null) return false;
        if (root != excludeNode && root.val == x) return true;
        if (root.val < x) return searchBST(root.right, excludeNode, x);
        return searchBST(root.left, excludeNode, x);
    }
}

Time Complexity: O(n) and Space Complexity: O(n)

The "Two Sum IV - Input is a BST" problem is a variation of the well-known "Two Sum" problem, but the input is a Binary Search Tree (BST). The goal is to find two nodes in the BST whose values add up to a given target value.

This problem can be efficiently solved using the properties of the BST and leveraging different data structures such as hash sets or utilizing in-order traversal with two pointers to achieve an optimal solution.

Problem Statement

Given a Binary Search Tree and a target value, return true if there exist two elements in the BST such that their sum is equal to the target value.

The tree node structure is defined as above. The task is to return whether there exist two nodes in the BST whose values sum up to the target value.

Approach

To solve this problem efficiently, we can use two primary approaches:

• Using a Hash Set: We perform a Depth-First Search (DFS) traversal of the BST, and for each node, we check if the complement of the current node's value (i.e., target - node.val) is already present in the hash set. If it is, we've found two nodes that sum to the target. If not, we add the current node’s value to the hash set and continue the search.
• Using In-Order Traversal with Two Pointers: Another approach is to perform an in-order traversal to get a sorted array of node values, and then use two pointers (one at the beginning and one at the end) to find the two nodes whose sum equals the target.

The hash set approach is more direct and generally easier to implement, while the two-pointer technique requires a sorted list and can be more efficient in terms of space complexity.

Algorithm

The algorithm for the hash set approach is as follows:

1. Initialize an empty hash set.
2. Perform a DFS traversal of the tree. For each node:
• Calculate the complement of the current node's value (complement = target - node.val).
• If the complement is found in the hash set, return true (since we've found a pair that sums to the target).
• If not, add the current node’s value to the hash set and continue the DFS traversal.
3. If the traversal completes and no such pair is found, return false.

This approach ensures that we can find the solution in a single pass of the tree, making it very efficient.

Example

Consider the following Binary Search Tree:

               5
              / \
             3   6
            / \    \
           2   4    7
        

Suppose the target value is 9. We need to check if there exist two nodes in the tree whose values sum up to 9. The two nodes 2 and 7 sum to 9, so the answer is true.

Time Complexity

The time complexity of this solution is O(n), where n is the number of nodes in the BST. This is because we perform a DFS traversal of the tree, visiting each node exactly once.

The space complexity is O(n) due to the hash set, which stores the values of the nodes. In the worst case, the size of the hash set will be O(n) if all node values are unique.

Optimized Approach

The hash set approach is already quite optimized, achieving linear time complexity. However, if we use the two-pointer technique (by performing an in-order traversal to get a sorted list of nodes and then using two pointers), the space complexity can be reduced to O(h), where h is the height of the tree (due to recursion stack space). This requires extra work to store the node values and sort them, so the hash set approach is generally preferred for simplicity and efficiency.

Time Complexity (Optimized)

The time complexity remains O(n), where n is the number of nodes in the tree. The space complexity for the two-pointer approach could be O(h), where h is the height of the tree due to the recursion stack, but for the hash set approach, it is O(n) in the worst case.

Conclusion

The "Two Sum IV - Input is a BST" problem can be solved efficiently using a hash set to keep track of the values visited during a DFS traversal. The solution has a time complexity of O(n) and a space complexity of O(n), where n is the number of nodes in the tree. While the two-pointer approach with in-order traversal could reduce space complexity, the hash set approach is simpler and performs well in practice.