Problem Description

Given the root of a Binary Search Tree (BST) and an integer k, determine if there exist two elements within the BST whose sum equals k. Return true if such a pair exists, otherwise return false.

Solution Explanation

Two approaches are presented to solve this problem:

Approach 1: Depth-First Search (DFS) with a Set

This approach uses a depth-first search to traverse the BST. A set (or HashSet in other languages) is used to store the values encountered during the traversal. For each node visited, the algorithm checks if k - node.val exists in the set. If it does, it means a pair with the sum k has been found, and true is returned. Otherwise, the node's value is added to the set, and the search continues recursively to the left and right subtrees.

Time Complexity: O(N), where N is the number of nodes in the BST. In the worst case, the entire tree needs to be traversed. Space Complexity: O(H), where H is the height of the BST. This is due to the recursive call stack in the DFS and the space used by the set (which can be at most N in the worst case of a skewed tree but is generally proportional to the height for balanced trees). In a balanced tree, H is log(N).

Approach 2: Breadth-First Search (BFS) with a Set

This approach is similar to the DFS approach but utilizes a breadth-first search instead. A queue is used to store nodes to be visited. The algorithm iterates through the queue level by level, checking for the complement (k - node.val) in the set for each node. If found, it returns true. Otherwise, the node's value is added to the set, and its children are added to the queue.

Time Complexity: O(N), similar to DFS, the entire tree is traversed. Space Complexity: O(W), where W is the maximum width of the BST. In a balanced tree, W is proportional to N. In a skewed tree, it would be O(1). The queue can hold at most all nodes at the widest level. The set's space complexity remains similar to the DFS approach.

Code Implementation (Multiple Languages)

Approach 1 (DFS):

Python:

class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        visited = set()
 
        def dfs(node):
            if not node:
                return False
            if k - node.val in visited:
                return True
            visited.add(node.val)
            return dfs(node.left) or dfs(node.right)
 
        return dfs(root)

Java:

import java.util.HashSet;
import java.util.Set;
 
class Solution {
    private Set<Integer> visited = new HashSet<>();
 
    public boolean findTarget(TreeNode root, int k) {
        return dfs(root, k);
    }
 
    private boolean dfs(TreeNode node, int k) {
        if (node == null) {
            return false;
        }
        if (visited.contains(k - node.val)) {
            return true;
        }
        visited.add(node.val);
        return dfs(node.left, k) || dfs(node.right, k);
    }
}

C++:

class Solution {
public:
    unordered_set<int> visited;
    bool findTarget(TreeNode* root, int k) {
        return dfs(root, k);
    }
    bool dfs(TreeNode* node, int k) {
        if (!node) return false;
        if (visited.count(k - node->val)) return true;
        visited.insert(node->val);
        return dfs(node->left, k) || dfs(node->right, k);
    }
};

(Other languages - Go, TypeScript, Rust - follow similar patterns using their respective Set/HashSet implementations and recursive DFS)

Approach 2 (BFS):

Python:

from collections import deque
 
class Solution:
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        q = deque([root])
        visited = set()
        while q:
            node = q.popleft()
            if not node:
                continue
            if k - node.val in visited:
                return True
            visited.add(node.val)
            q.append(node.left)
            q.append(node.right)
        return False
 

Java:

import java.util.*;
 
class Solution {
    public boolean findTarget(TreeNode root, int k) {
        Queue<TreeNode> q = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        q.offer(root);
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (node == null) continue;
            if (visited.contains(k - node.val)) return true;
            visited.add(node.val);
            q.offer(node.left);
            q.offer(node.right);
        }
        return false;
    }
}

(Similar BFS implementations can be done in other languages following the same queue-based approach and using their respective Set/HashSet implementations.)

Note: The TreeNode definition would need to be appropriately defined in each language (e.g., using classes in Python/Java/TypeScript, structs in C++/Go, and potentially Rc<RefCell> in Rust for shared ownership when dealing with tree nodes). The code snippets above focus primarily on the core algorithm.