Code Implementation

# 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

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

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

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

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

import java.util.HashSet;

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

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {boolean}
 */
var findTarget = function(root, k) {
    const seen = new Set();
    function dfs(node) {
        if (!node) return false;
        if (seen.has(k - node.val)) return true;
        seen.add(node.val);
        return dfs(node.left) || dfs(node.right);
    }
    return dfs(root);
};
      

Problem Description

Given the root of a Binary Search Tree (BST) and an integer k, determine if there exist two distinct elements in the BST such that their sum equals k.

• You must return true if there are two different nodes in the BST whose values add up to k; otherwise, return false.
• Each input will have exactly one BST and one target value k.
• You may not use the same element twice (i.e., you cannot use the same node twice).
• The BST may contain negative values and duplicates are not allowed.

Thought Process

The problem asks if there are two distinct nodes in a BST whose values sum to a given target k. At first glance, this is similar to the classic "Two Sum" problem, but the input is a tree, not a flat array.

A brute-force approach would involve checking all pairs of nodes, but this is inefficient for trees. Since a BST allows for in-order traversal to access values in sorted order, we can potentially leverage this property.

However, to efficiently check whether the complement (i.e., k - node.val) of the current node's value has been seen before, we can use a hash set. As we traverse the tree, for each node, we check if its complement already exists in the set. If it does, we've found our answer. If not, we add the current node's value to the set and continue traversing.

This approach is inspired by the array-based "Two Sum" hash set solution, adapted to tree traversal.

Solution Approach

Here is a step-by-step breakdown of the optimized solution using a hash set:

1. Initialize a hash set: This set will store values of nodes we've already visited.
2. Traverse the BST: Use depth-first search (DFS) to visit every node in the tree.
3. Check for the complement: For each node, calculate k - node.val. If this value is already in the set, it means we've previously seen a node whose value, added to the current node's value, equals k. In this case, return true.
4. Add current value to the set: If the complement is not found, add the current node's value to the set so future nodes can match against it.
5. Continue traversal: Recursively check the left and right subtrees.
6. Return false if not found: If we traverse the entire tree without finding such a pair, return false.

This method is efficient because hash set lookups are O(1) on average, and we only traverse each node once.

Example Walkthrough

Example: Suppose the BST is:

        5
       / \
      3   6
     / \   \
    2   4   7
  

Let k = 9.

1. Start at root (5): 9 - 5 = 4. 4 is not in the set. Add 5 to set.
2. Go left to 3: 9 - 3 = 6. 6 not in set. Add 3.
3. Go left to 2: 9 - 2 = 7. 7 not in set. Add 2.
4. Back up, go right to 4: 9 - 4 = 5. 5 is in set! Found a pair: (4, 5).

The function returns true as soon as it finds this pair.

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(N²), since you would have to check all pairs of nodes.
  • Space Complexity: O(H), where H is the height of the tree (for recursion stack).
• Optimized hash set approach:
  • Time Complexity: O(N), where N is the number of nodes, since we visit each node once.
  • Space Complexity: O(N), for the hash set storing up to N node values in the worst case.

The optimized approach is significantly better for large trees.

Summary

The "Two Sum IV - Input is a BST" problem is a tree-based variation of the popular Two Sum problem. By leveraging a hash set during a tree traversal, we can efficiently determine if any two distinct nodes sum to the target value. This approach avoids the inefficiency of checking all pairs and demonstrates how classic array-based solutions can be adapted to trees by combining traversal techniques with auxiliary data structures.