653 - Two Sum IV - Input is a BST

Difficulty: Easy | Pattern: Tree + HashSet | Company tags: Amazon, Google, Facebook

Problem Statement

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.

Example 1:

Input: root = [5,3,6,2,4,null,7], k = 9
Output: true  (3 + 6 = 9)

Example 2:

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

Approach: DFS + HashSet — O(n), O(n)

Key insight: Traverse tree, for each node check if k - node.val already seen. If yes, found a pair.

def findTarget(root, 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)

Dry Run

Tree: 5(root), left=3(2,4), right=6(null,7), k=9

DFS order: visit 5 → seen={5}; visit 3 → 9-3=6 not in seen → seen={5,3}; visit 2 → seen={5,3,2}; visit 4 → seen={5,3,2,4}; visit 6 → 9-6=3 in seen → True ✓

Note on BST Property

The BST property (sorted order) is not directly used in the set approach. A smarter O(n) time + O(h) space approach uses two BST iterators (one from min, one from max) moving inward like a two-pointer.

Edge Cases

• k equals 2 * node.val — same node counted twice: we check complement first, then add. So if node.val = k/2, its complement has not been added yet, correctly returns false for that node alone.
• Single node → always false (no second element)

Complexity

• Time: O(n)
• Space: O(n)