Two Sum in a BST

Two Sum in a BST takes the classic Two Sum question and changes the input from a flat array to a binary search tree. The twist rewards anyone who remembers one fact about BSTs: an in-order traversal hands you the values already sorted.

The slow way first

The brute-force idea: for every node, search the tree again for k - value. That is O(n) searches, each O(h) deep, and it has to be careful not to match a node with itself. It works but it is fiddly and wastes the structure we were handed.

The question to ask: what do I already know about a BST that an array does not give me for free? A BST in-order traversal produces a sorted sequence. Once the data is sorted, Two Sum becomes the easy two-pointer sweep — no hashing, no repeated searches.

The idea: flatten, then two-pointer

Do it in two clean phases. Phase one: walk the tree in-order and collect the values into a list arr. Because it is a BST, arr comes out sorted. Phase two: put one pointer lo at the front and one pointer hi at the back, and compare arr[lo] + arr[hi] to k. Too big means shrink the sum by moving hi left; too small means grow it by moving lo right; equal means we found the pair.

The key insight: a sorted list lets each comparison tell us which pointer to move, so the two pointers only ever march toward each other and the whole sweep is one pass.

Walk through it

Step through the animation. First the in-order walk lights up the nodes smallest-to-largest and drops each value into the sorted row underneath. Then lo starts at 1 and hi at 14. Their sum 15 is too big, so hi steps left; then 11 is too small, so lo steps right; and the pointers keep closing in until 5 + 7 = 12 hits the target.

Pseudocode

arr = []
in-order traverse the BST, appending each value to arr   # arr is now sorted
lo, hi = 0, len(arr) - 1
while lo < hi:
    s = arr[lo] + arr[hi]
    if s > k:        hi = hi - 1     # sum too big, shrink it
    elif s < k:      lo = lo + 1     # sum too small, grow it
    else:            return True     # found a pair
return False

The Python solution

def find_target(root, k):
    arr = []
    inorder(root, arr)        # fills arr in sorted order
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        s = arr[lo] + arr[hi]
        if s > k:
            hi -= 1
        elif s < k:
            lo += 1
        else:
            return True
    return False

• inorder(root, arr) does the left-root-right walk, appending each node value; because of the BST ordering, arr lands sorted.
• lo and hi start at the two ends of the sorted list.
• s = arr[lo] + arr[hi] is the current pair sum we are testing.
• If s > k the pair is too big, so we move hi down to a smaller value.
• If s < k the pair is too small, so we move lo up to a larger value.
• If they are equal we return True immediately; if the pointers meet without a hit, no pair exists.

Complexity

The flatten-and-sweep approach is O(n) time and O(n) space (for the list). That space is the cost of turning the tree into something the two-pointer trick can sweep. A more advanced solution uses a hash set during traversal for the same time but still O(n) space; the sorted-list view is the clearest to reason about.

When this pattern shows up

Practice