☕ DSA Java Articles

Topics › Binary Search Trees › Practice Problems

Two sum in BST

Hard TUF ID 99 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given the root of a binary search tree with distinct keys and an integer k. Return true if there are two different nodes whose keys add up to k, and false otherwise. A node cannot be paired with itself, so a single key equal to k / 2 is not enough.

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

Example 1

        5
       / \
      3   6
     / \   \
    2   4   7

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

Example 2

same tree, k = 28   answer = false

The largest possible pair is 6 + 7 = 13.

Example 3

      2
     / \
    1   3

k = 6    answer = false    // 3 + 3 would use the same node twice

Approach 1: Brute force, search for every complement

Intuition. For each node with key v, the partner it needs is k - v. A BST can answer “is this key present?” in O(h) by walking down from the root. So visit every node and run one search for its complement. Since keys are distinct, a complement equal to v itself could only be the same node, and must be skipped.

On a balanced tree this already beats the O(n^2) scan over all pairs, because each search uses the ordering. But it repeats a root-to-leaf walk for every node, and on a chain-shaped tree each walk is as long as the tree.

Algorithm.

  1. Traverse the tree. At each node compute need = k - node.val (in long, because the subtraction can overflow int for extreme inputs).
  2. If need != node.val and a BST search from the root finds need, return true.
  3. Otherwise continue into both children. Return false when the traversal ends.
static boolean bruteForce(TreeNode root, int k) {
    return hasPartner(root, root, k);
}

static boolean hasPartner(TreeNode node, TreeNode root, int k) {
    if (node == null) return false;
    long need = (long) k - node.val;                 // long: k - val can overflow int
    if (need != node.val && contains(root, need)) return true;   // distinct keys: need == val would be this same node
    return hasPartner(node.left, root, k) || hasPartner(node.right, root, k);
}

static boolean contains(TreeNode root, long key) {
    TreeNode cur = root;
    while (cur != null) {
        if (cur.val == key) return true;
        cur = key < cur.val ? cur.left : cur.right;
    }
    return false;
}

Complexity. Time O(n · h): n searches, each O(h). That is O(n log n) on a balanced tree and O(n^2) on a chain. Space O(h) for the traversal’s recursion.

Approach 2: Better, in-order list plus two pointers

Intuition. The in-order traversal of a BST lists its keys in ascending order. Once we have a sorted list, Two Sum on a sorted array is a classic two-pointer sweep: put lo at the smallest key and hi at the largest.

Each step removes one key from consideration for good, so the sweep is linear. The loop condition lo < hi guarantees the two pointers refer to different nodes.

Algorithm.

  1. Collect the keys with an in-order traversal.
  2. Set lo = 0, hi = size - 1.
  3. While lo < hi: compare the sum with k and move one pointer, or return true on a match.
  4. Return false.
static boolean better(TreeNode root, int k) {
    List<Integer> sorted = new ArrayList<>();
    inorder(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 inorder(TreeNode node, List<Integer> out) {
    if (node == null) return;
    inorder(node.left, out);
    out.add(node.val);
    inorder(node.right, out);
}

Complexity. Time O(n): one traversal plus one linear sweep. Space O(n) for the list.

The time is now optimal, since in the worst case every key must be looked at. What remains wasteful is storing all n keys when the sweep only ever looks at two of them at a time. (A hash set of seen keys also gives O(n) time and O(n) space and works on any binary tree, but it ignores the BST order entirely.)

Approach 3: Optimal, two BST iterators

Intuition. The two-pointer sweep needs exactly two operations: “give me the next larger key” for lo and “give me the next smaller key” for hi. We can produce both lazily, straight from the tree, without materialising the list.

A BST iterator does this with a stack. To get keys in ascending order, push the leftmost path; the top of the stack is the smallest key. After popping a node, push the leftmost path of its right child, because those keys come next. For descending order, mirror everything: push the rightmost path and, after popping, push the rightmost path of the left child. Each stack holds at most one root-to-leaf path, so O(h) memory.

With one ascending and one descending iterator, the two-pointer sweep from Approach 2 runs unchanged. Because keys are distinct, lo < hi still means the two values come from different nodes. And whenever lo < hi, there is at least one more key above lo (namely hi) and one below hi, so neither iterator is ever asked for a key it does not have.

Algorithm.

  1. If the tree is empty, return false.
  2. Create an ascending iterator and a descending iterator. Let lo be the first key of the ascending one and hi the first of the descending one.
  3. While lo < hi: if lo + hi == k return true; if smaller, advance the ascending iterator; if larger, advance the descending iterator.
  4. Return false.
static boolean optimal(TreeNode root, int k) {
    if (root == null) return false;
    BSTIterator ascending = new BSTIterator(root, false);
    BSTIterator descending = new BSTIterator(root, true);
    int lo = ascending.next(), hi = descending.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 = ascending.next(); else hi = descending.next();
    }
    return false;
}

/** In-order iterator holding at most h nodes; reverse = true yields keys from largest to smallest. */
static class BSTIterator {
    private final Deque<TreeNode> stack = new ArrayDeque<>();
    private final boolean reverse;

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

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

    private void pushChain(TreeNode node) {      // the leftmost (or rightmost) path below node
        while (node != null) {
            stack.push(node);
            node = reverse ? node.right : node.left;
        }
    }
}

Dry run on Example 1 with k = 14 (a false case, so we see the whole sweep):

lo hi lo + hi action
2 7 9 too small, advance ascending
3 7 10 too small, advance ascending
4 7 11 too small, advance ascending
5 7 12 too small, advance ascending
6 7 13 too small, advance ascending
7 7   lo == hi: same node, stop, return false

The last row is exactly why the loop uses lo < hi: 7 + 7 = 14 is not a valid pair.

Complexity. Time O(n): each iterator pushes and pops every node at most once over the whole run, so the total work is linear even though a single next() can cost up to O(h). Space O(h) for the two stacks.

Edge cases and pitfalls