Problem 17.7 · Binary Search TreesEasy

Two Sum in a BST

PatternBST Ordering Hash Map Lookup (Complement)Two Pointers: Opposite Ends

What it teaches: Reusing array patterns on a tree: in-order gives a sorted list for two pointers, or a hash set during any traversal.

Practise it on judges as “Two Sum IV - Input is a BST”.

The problem

Return true if two different nodes in the BST add up to k.

Example 1

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

Example 2

Input: same tree, k = 28
Output: false

Constraints

1 ≤ nodes ≤ 10⁴

Pattern clues in the wording

→ Pair sum on ordered data

These clues point to BST Ordering: Use left < node < right to skip half the tree, and in-order traversal to visit values in sorted order.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public boolean findTarget(TreeNode root, int k) {
        return false;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	root = [5,3,6,2,4,null,7] k = 9	true
2	root = [5,3,6,2,4,null,7] k = 28	false

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. DFS with a hash set · O(n)2. In-order list + two pointers · O(n)

DFS with a hash set

Time O(n) Space O(n)

Visit nodes; if k − value is in the set, return true; otherwise add the value.

Approach 1

import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean findTarget(TreeNode root, int k) {
        return dfs(root, k, new HashSet<>());
    }

    private boolean dfs(TreeNode n, int k, Set<Integer> seen) {
        if (n == null) return false;
        if (seen.contains(k - n.val)) return true;
        seen.add(n.val);
        return dfs(n.left, k, seen) || dfs(n.right, k, seen);
    }
}

Verdict: Works for any binary tree.

In-order list + two pointers

Time O(n) Space O(n)

Collect values in sorted order, then move pointers inward from both ends.

Approach 2

import java.util.ArrayList;
import java.util.List;

class Solution {
    public boolean findTarget(TreeNode root, int k) {
        List<Integer> a = new ArrayList<>();
        inorder(root, a);
        int l = 0, r = a.size() - 1;
        while (l < r) {
            int s = a.get(l) + a.get(r);
            if (s == k) return true;
            if (s < k) l++; else r--;
        }
        return false;
    }

    private void inorder(TreeNode n, List<Integer> a) {
        if (n == null) return;
        inorder(n.left, a); a.add(n.val); inorder(n.right, a);
    }
}

Verdict: Uses the BST ordering.

Before you submit

Edge cases and common mistakes

Test these inputs

Single node
k = 2 × a value (the same node can't be used twice)

Mistakes people make

Adding the value to the set before checking (matches a node with itself).

Interview

Follow-up questions

Can you do it in O(h) extra space?

Command Palette