☕ DSA Java Articles

Topics › Binary Search Trees › Practice Problems

Two Sum In BST | Check if there exists a pair with Sum K

Hard TUF ID 2774 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given the root of a binary search tree and an integer k. Return true if there are two different nodes whose keys add up to k, and false otherwise. Keys in a BST are distinct, so “two different nodes” means two different keys; a single key used twice does not count.

Constraints (LeetCode version): up to 10^4 nodes, keys in [-10^4, 10^4], k in [-10^5, 10^5]. The code below does its sums in long, so it stays correct for any 32-bit keys.

All examples use this tree (in-order: 2 3 4 5 6 7):

        5
       / \
      3   6
     / \   \
    2   4   7

Example 1

k = 9
answer = true        // 2 + 7 (also 3 + 6 and 4 + 5)

Example 2

k = 28
answer = false       // the largest possible sum is 6 + 7 = 13

Example 3

k = 14
answer = false       // 7 + 7 would use the same node twice

Approach 1: Hash set, the Two Sum way

Intuition. Forget that this is a BST and treat it as a bag of numbers. While visiting nodes in any order, ask “have I already seen k - key?”. A hash set answers that in constant time. Adding the current key after the lookup is what stops a node from pairing with itself: when we look up 7 at node 7 for k = 14, the set does not contain 7 yet.

Algorithm.

  1. Traverse the tree (preorder here) with an empty set seen.
  2. At each node, if k - node.val is in seen, return true.
  3. Otherwise add node.val and continue into both children.
  4. Return false when the traversal finishes.
static boolean withHashSet(TreeNode root, int k) {
    return findWithSet(root, k, new HashSet<>());
}

static boolean findWithSet(TreeNode node, int k, Set<Long> seen) {
    if (node == null) return false;
    if (seen.contains((long) k - node.val)) return true;     // long: k - val can overflow int
    seen.add((long) node.val);                               // add after the check so a node never pairs with itself
    return findWithSet(node.left, k, seen) || findWithSet(node.right, k, seen);
}

The set stores Long values and the complement is computed as (long) k - node.val, because k - node.val can overflow int when keys are near the limits.

Complexity. Time O(n): every node is visited once, with O(1) average set work. Space O(n) for the set, plus O(h) recursion. This works on any binary tree; it never uses the ordering.

Approach 2: In-order list plus two pointers

Intuition. The in-order traversal of a BST is sorted, and on a sorted array Two Sum has a classic answer: one pointer at the smallest key, one at the largest. If their sum is too small, the smallest key is useless: even its best partner, the largest remaining key, is not enough, so drop it by moving lo right. If the sum is too large, the largest key is useless for the symmetric reason, so move hi left. Every step discards one key that provably has no partner among the remaining keys, so no valid pair is ever skipped.

Algorithm.

  1. Collect the keys in in-order into a list (sorted).
  2. Set lo = 0, hi = size - 1.
  3. While lo < hi: if the sum equals k, return true; if it is smaller, lo++; otherwise hi--.
  4. Return false.
static boolean inorderTwoPointers(TreeNode root, int k) {
    List<Integer> sorted = new ArrayList<>();
    collectInorder(root, sorted);
    int lo = 0, hi = sorted.size() - 1;
    while (lo < hi) {
        long sum = (long) sorted.get(lo) + sorted.get(hi);
        if (sum == k) return true;
        if (sum < k) lo++; else hi--;
    }
    return false;
}

static void collectInorder(TreeNode node, List<Integer> out) {
    if (node == null) return;
    collectInorder(node.left, out);
    out.add(node.val);
    collectInorder(node.right, out);
}

Complexity. Time O(n): one traversal and at most n - 1 pointer moves. Space O(n) for the list.

The loop condition lo < hi is what forbids using one node twice. The list is no smaller than the hash set, so this approach is not better yet. It is the stepping stone: the two pointers only ever move inward one step at a time, so they never need random access into the list.

Approach 3: Optimal, two BST iterators

Intuition. A pointer that only moves forward through the in-order sequence is exactly a BST iterator: a stack holding the left spine of the unvisited part, whose top is the next smallest key. Mirror it (push right spines, and after popping go to the left child) and you get an iterator that yields keys from the largest down. Two iterators replace the two indices, and each stack holds at most one root-to-leaf path, so memory drops from O(n) to O(h).

The iterator calls inside the loop are always safe. While lo < hi, the ascending iterator has not yet produced hi, so it still has at least one key to give, and the descending iterator still has lo ahead of it.

Algorithm.

  1. Create an ascending iterator and a descending iterator over the tree.
  2. lo = asc.next(), hi = desc.next().
  3. While lo < hi: if lo + hi == k, return true; if the sum is smaller, lo = asc.next(); otherwise hi = desc.next().
  4. Return false.
static boolean bstIterators(TreeNode root, int k) {
    if (root == null) return false;
    BSTIterator asc = new BSTIterator(root, false);
    BSTIterator desc = new BSTIterator(root, true);
    int lo = asc.next(), hi = desc.next();
    while (lo < hi) {                                        // distinct keys: lo < hi means two different nodes
        long sum = (long) lo + hi;
        if (sum == k) return true;
        if (sum < k) lo = asc.next(); else hi = desc.next();
    }
    return false;
}

/** In-order iterator over a BST using a stack of at most h nodes; reverse = true walks from the largest key down. */
static class BSTIterator {
    private final Deque<TreeNode> stack = new ArrayDeque<>();
    private final boolean reverse;

    BSTIterator(TreeNode root, boolean reverse) {
        this.reverse = reverse;
        pushAll(root);
    }

    int next() {
        TreeNode node = stack.pop();
        pushAll(reverse ? node.left : node.right);
        return node.val;
    }

    private void pushAll(TreeNode node) {
        while (node != null) {
            stack.push(node);
            node = reverse ? node.right : node.left;
        }
    }
}

Dry run with k = 11. Stacks are written bottom to top.

step lo hi sum action asc stack after desc stack after
start 2 7     [5, 3] [5, 6]
1 2 7 9 9 < 11, advance lo [5, 4] [5, 6]
2 3 7 10 10 < 11, advance lo [5] [5, 6]
3 4 7 11 found, return true    

When asc popped 3, it pushed the left spine of 3’s right child, which is just 4; that is why 4 appears on its stack in step 1.

Complexity. Time O(n): each iterator pushes and pops every node at most once, so all next() calls together cost O(n), amortised O(1) each. Space O(h) for the two stacks: O(log n) on a balanced tree.

Edge cases and pitfalls