Find a pair with given target in BST

Given the root of a binary search tree and an integer target, return true if there exist two different nodes in the BST whose values sum to target, and false otherwise.

The tree is given in level-order (breadth-first), using null for missing children.

Hints

· Stuck? Reveal one nudge at a time.

This is two-sum — think about how you solve it on an array.

A BST's inorder traversal gives you the values already sorted.

On a sorted array, use two pointers from both ends and move based on the sum.

Common doubts

Both are O(n) time, but the two-pointer sweep uses O(1) extra beyond the array and leans on the BST's natural ordering.

No — it works on any binary tree, since it only checks complements. That's its advantage and why it's the 'brute' baseline here.

Keep the two pointers strictly apart (i < j); the hash-set version only checks against previously-seen nodes.

Interview follow-ups

· What an interviewer asks next.

Walk one BST ascending and the other descending in lockstep — the two-pointer idea across two iterators.

Return the two values at the pointers (or the node and its complement) when the sum matches.

Fun facts

This is LeetCode 653 (Two Sum IV) — the tree flavour of the most-asked array problem.
The two-pointer sweep is the same skeleton used to merge two sorted BSTs.

Asked at

AmazonMicrosoftFacebook

Frequently Sometimes Occasionally

Example 1

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

Example 2

Input: root = [5, 3, 6, 2, 4, null, 7], target = 28
Output: false
No two distinct node values sum to 28.

Constraints

- The number of nodes is in the range [1, 10^4] - -10^5 <= Node.val <= 10^5 - -2 * 10^5 <= target <= 2 * 10^5 - All Node.val are unique

This is two-sum on a tree. The hash-set approach is the direct translation: traverse the tree, and for each node check whether its complement target - val has already been seen. It's O(n) time but O(n) extra space and doesn't use the BST ordering at all.

The approach that uses the BST flattens it with an inorder traversal into a sorted array, then runs the classic two-pointer sweep: a pointer at each end, move the left pointer right when the sum is too small and the right pointer left when it's too big. Same O(n) time, but the logic is the standard sorted-array two-sum — and it generalises to the "two BSTs" variant.

Prerequisites

Before you start

· Concepts used directly in the solution.

Two-sum. Complement lookup, or two pointers on a sorted array.

Inorder = sorted. A BST's inorder traversal is ascending.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“Must the two nodes be different?”

Yes — a single node used twice does not count.

“Can values be negative?”

Assume the given range; the logic is unchanged either way.

The ideal opening — say it like this

Inorder gives me the values sorted, then it's the standard two-pointer two-sum from both ends.

If I can't afford the array, a hash set of seen values with a complement check also works in one pass.

Understand the problem

Worked example — BST [5, 3, 6, 2, 4, null, 7], target = 9

inorder = [2, 3, 4, 5, 6, 7]
i=2,j=7 -> 9 == target -> true

Key observations

1Aha

Inorder yields a sorted array

That turns the tree problem into sorted-array two-sum.

2Aha

Two pointers exploit monotonicity

Too-small sum ⇒ advance the left pointer; too-big ⇒ retreat the right pointer.

3Aha

Hash set needs no ordering

The complement-check works on any binary tree, at the cost of O(n) space.

Brute force vs optimal

	Hash set of seen	Inorder + two pointers
Idea	Check target - val against a set while traversing	Flatten to sorted, sweep from both ends
Time	O(n)	O(n)
Space	O(n)	O(n) for the array, O(1) sweep
Uses BST order

Both are O(n); the two-pointer version leans on the BST's sorted inorder. Full code is in the Approaches selector below.

Summary

Key takeaway

Inorder-flatten the BST to a sorted array, then two-pointer two-sum from both ends. Or, without the array, traverse and check each node's complement against a hash set. Both O(n).

a = inorder(root)          # sorted
i, j = 0, len(a)-1
while i < j:
    s = a[i] + a[j]
    if s == target: return True
    if s < target: i += 1 else: j -= 1
return False