Problem statement

Given the root of a binary search tree with distinct values and an integer k, return true if there are two different nodes whose values add up to k, and false otherwise.

Example 1

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

Example 2

Input: root = [5,3,6,2,4,null,7], k = 28
Output: false
Explanation: The two largest values add up to only 13.

Example 3

Input: root = [1], k = 2
Output: false
Explanation: 1 + 1 would use the same node twice.

Constraints

• The number of nodes in the tree is in the range [1, 10^4]
• -10^4 <= Node.val <= 10^4
• All values in the tree are distinct
• -10^5 <= k <= 10^5

Hints for Two Sum IV - Input is a BST

1. Hint 1

   This is Two Sum, with the numbers stored in a tree instead of an array.

2. Hint 2

   Walk the tree; for each value v, ask whether k - v has already been seen. A hash set answers in O(1).

3. Hint 3

   Alternatively, an inorder walk gives the values sorted, and two pointers from both ends find a pair in one pass.

How to solve Two Sum IV - Input is a BST

Visit every node once, keeping a set of the values seen so far. A pair summing to k exists exactly when, at some node, its complement k - val is already in the set.

Approach

1. Start with an empty set and traverse the tree (any order).
2. At each node with value v: if k - v is in the set, return true.
3. Otherwise add v to the set and continue.
4. If the traversal ends, return false.

Why it works

If nodes a and b (visited in that order) satisfy a + b = k, then when b is visited a is already in the set and the check succeeds. Conversely the check only succeeds against a value stored at a different, earlier node, so the same node is never used twice.

Complexity

• Time — O(n)
• Space — O(n) for the set (the sorted-list two-pointer version also needs O(n), or O(h) with two BST iterators)

Pitfalls

• Check the complement before inserting the current value, or v + v = k would match a single node.
• The BST order is not needed for the hash-set solution — it is what makes the two-pointer one possible.

Reference solution

Python

from typing import Optional

def findTarget(root: Optional[TreeNode], k: int) -> bool:
    seen = set()
    stack = [root] if root is not None else []
    while stack:
        node = stack.pop()
        if k - node.val in seen:
            return True
        seen.add(node.val)
        if node.left is not None:
            stack.append(node.left)
        if node.right is not None:
            stack.append(node.right)
    return False

Java

public static boolean findTarget(TreeNode root, int k) {
    Set<Integer> seen = new HashSet<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    if (root != null) stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        if (seen.contains(k - node.val)) return true;
        seen.add(node.val);
        if (node.left != null) stack.push(node.left);
        if (node.right != null) stack.push(node.right);
    }
    return false;
}

C++

bool findTarget(TreeNode* root, int k) {
    unordered_set<int> seen;
    vector<TreeNode*> stack;
    if (root) stack.push_back(root);
    while (!stack.empty()) {
        TreeNode* node = stack.back();
        stack.pop_back();
        if (seen.count(k - node->val)) return true;
        seen.insert(node->val);
        if (node->left) stack.push_back(node->left);
        if (node->right) stack.push_back(node->right);
    }
    return false;
}

JavaScript

var findTarget = function(root, k) {
    var seen = new Set();
    var stack = root === null ? [] : [root];
    while (stack.length > 0) {
        var node = stack.pop();
        if (seen.has(k - node.val)) return true;
        seen.add(node.val);
        if (node.left !== null) stack.push(node.left);
        if (node.right !== null) stack.push(node.right);
    }
    return false;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More hash table problems

• Level of a Node in Binary Tree Easy
• Sum of Leaf Nodes at Minimum Level Easy
• Count BST Nodes That Lie in a Given Range Easy
• Nodes at Odd Levels Easy
• Kth Largest Element in BST Easy
• Ceil in BST Easy