DSA Tracker

Visualize

Two Sum IV - Input is a BST

Two BST iterators squeeze inward, exactly like two pointers on a sorted array

time O(n)space O(h) — the two stacks together never exceed the tree's height

A BST's inorder walk is already sorted, so two-sum on it is the same squeeze used on a sorted array: one pointer starts at the smallest value and one at the largest, and whichever side's sum is wrong gets advanced toward the middle. Instead of buffering the whole sorted list, two explicit stacks act as lazy iterators — one descending left for the next-smallest value, one descending right for the next-largest — so each step only materializes the one node it needs.

Details

Animated on: root=[5,3,6,2,4,null,7], k=9 — return true if two distinct node values sum to k. Expected: true (3 + 6 = 9).

Problem:Two Sum IV - Input is a BSTEasy

Two BST iterators squeeze inward, exactly like two pointers on a sorted array

step 1 / 9

2
3
4
5
6
7

Call stack

low stack: []high stack: []

Point two iterators at the root, 5: node1 will crawl left to find the smallest unconsumed value, node2 will crawl right to find the largest. Target k=9.

Pseudocode
1FUNCTION twoSumBST(root, k):
2low <- [], high <- []
3node1 <- root, node2 <- root
4WHILE true:
5  WHILE node1 != null: PUSH node1 TO low; node1 <- node1.left
6  WHILE node2 != null: PUSH node2 TO high; node2 <- node2.right
7  left <- TOP(low), right <- TOP(high)
8  IF left = right: RETURN false
9  IF left.val + right.val = k: RETURN true
10  ELSE IF left.val + right.val < k: node1 <- POP(low).right
11  ELSE: node2 <- POP(high).left

← / → step · space play · Home restart

Every step in words

Show all 9 steps
  1. Point two iterators at the root, 5: node1 will crawl left to find the smallest unconsumed value, node2 will crawl right to find the largest. Target k=9.
  2. Push 5 onto the low stack and step to its left child. A BST's left subtree is always smaller, so descending left reaches the next smallest not-yet-seen value.
  3. Push 3 onto the low stack and step to its left child. A BST's left subtree is always smaller, so descending left reaches the next smallest not-yet-seen value.
  4. Push 2 onto the low stack and step to its left child. A BST's left subtree is always smaller, so descending left reaches the next smallest not-yet-seen value.
  5. Push 5 onto the high stack and step to its right child. Descending right reaches the next largest not-yet-seen value.
  6. Push 6 onto the high stack and step to its right child. Descending right reaches the next largest not-yet-seen value.
  7. Push 7 onto the high stack and step to its right child. Descending right reaches the next largest not-yet-seen value.
  8. Peek both stack tops without popping: low=2, high=7. These are the two closest values not yet ruled out.
  9. 2 + 7 = 9, which equals k=9 — a valid pair exists, so return true.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Two Sum IV - Input is a BST in the editorAll BST problemsBack to roadmap