STEP 14 · BINARY SEARCH TREES · TWO-POINTER SQUEEZE WITHOUT THE ARRAY · MEDIUM

Two Sum in BST (Pair With Sum K)

WHAT IT SAYS

Determine whether two nodes in a BST sum to a given target k.

WHAT IT'S REALLY ASKING

"On a sorted array you'd squeeze: fingers at both ends, too small → advance the left, too big → retreat the right. A BST IS that sorted array, folded — so the squeeze needs only two operations: 'next larger' and 'next smaller'. Build one iterator walking inorder forward and one walking it backward, and you have two pointers on a tree that was never flattened."

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Hash set during any traversal

O(n) time, O(n) space

Walk the tree in any order; for each value v, check whether k - v is already in a hash set, then add v. First hit wins.

WHERE THE WORK IS WASTED — Perfectly correct — and it would be the RIGHT answer on an unordered tree, which is exactly the indictment: this solution never reads the letters B-S-T. The invariant that insertion paid O(h) per node to maintain — the global sorted order — sits unused while a hash set rebuilds, in O(n) extra memory, the ability to find complements that sortedness already provides. When your solution to a structured problem is identical to your solution for the unstructured version, the structure is being wasted somewhere; here it's the entire ordering.

KEY OBSERVATION — THE UNLOCKlink

The squeeze needs only next-larger and next-smaller — iterators supply both.

Recall why the two-pointer squeeze works on sorted data, because the argument transfers wholesale: with fingers on the current smallest and largest candidates, their sum is simultaneously the smallest sum the right finger can make and the largest the left finger can make. Too small means the left element's BEST partner still fails — retire it, advance. Too large retires the right element. Each comparison eliminates one element forever; n elements, O(n) comparisons, done. (3Sum's engine, verbatim.) The intermediate solution — inorder-flatten to an array, then squeeze — is already O(n) time and beats the hash set philosophically by using the order. Its remaining flaw is the O(n) buffer, materialising the whole sorted sequence when the squeeze only ever inspects TWO positions at a time. So ask what the squeeze actually requires of its container: not random access, not the full array — just 'give me the next element' from each end. Those are streaming operations, and a BST supports both lazily. A FORWARD iterator: keep a stack of the path to the current node; initialise by pushing the left spine from the root (stack top = minimum); next() pops a node, pushes the left spine of its right child, returns the popped value. Ascending order, one node at a time. A BACKWARD iterator mirrors it — right spines, descending. Each iterator's stack holds one root-to-node path: O(h) space, and every edge is pushed and popped once across the iterator's lifetime, so all n next() calls cost O(n) total — amortised O(1) each. Now run the squeeze on the two iterators: pull lo from forward, hi from backward; while lo < hi as VALUES (the stop condition — when the fingers meet, every pair has been adjudicated): sum equal → found; too small → lo = forward.next(); too big → hi = backward.next(). The array was scaffolding; the squeeze runs on the tree directly, O(n) time, O(h) space. The layered lesson: hash set ignores the structure; flatten-then-squeeze uses the order but materialises it; dual iterators use the order AND leave it in place. Each layer discards one unnecessary thing.

Dual stack-iterators driving the squeeze

O(n) time — each node surfaces in at most one iterator — O(h) space for two path-stacks

Build nextLarger (stack seeded with the root's left spine) and nextSmaller (right spine). Pull one value from each; loop while lo's value < hi's value: on equality to k return true, on undershoot advance nextLarger, on overshoot advance nextSmaller. Return false when the fingers cross. (Same-node pairing is excluded by the strict lo < hi condition.)

WHAT YOU TRADED — Against the hash set: same time, O(h) versus O(n) space, but real implementation weight — two iterators with spine-pushing logic versus three lines with a set; on a shallow-and-wide tree the space win is decisive, in a timed interview the set may be the pragmatic opener with the iterators as the follow-up. The transferable lesson: before materialising a structure to run a two-pointer algorithm on it, list what the algorithm actually asks of its container — often just 'next from either end' — and check whether the structure can stream those answers in place.

WATCH THE IDEA RUN

WHAT THE TWO ITERATORS SEE (never materialised)

target 11

sum 15

space O(h), not O(n)

Flattening the BST into an array and running two pointers works — but it costs O(n) memory, and it throws away the fact that the tree was ALREADY sorted. The two pointers do not need an array. They need two questions answered: what is the next larger value, and what is the next smaller one.

step 1 / 6

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Stream the Squeeze

YOU'LL SEE IT AGAIN WHEN

A two-pointer or merge algorithm wants sorted sequential access, and the data lives in a structure whose canonical traversal IS that order.
The algorithm only ever inspects the frontier elements — next-from-left, next-from-right — never random positions, so full materialisation is scaffolding.
A path-stack iterator can amortise traversal to O(1) per step in O(h) space, replacing the O(n) flattened copy.

SAME BLUEPRINT, DIFFERENT PROBLEM

3 Sum (the squeeze engine on a real array)BST Iterator (the forward half of this machine, as its own problem)Merge Two BSTs (the same iterators driving a zipper instead of a squeeze)Two Sum IV — Input Is a BST

The bar isn't "solved it once." It's "could rebuild it from the observation."