Pattern visualizer
Two Sum in BST
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. 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)..
Two BST iterators squeeze inward, exactly like two pointers on a sorted array
Call 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.
1FUNCTION twoSumBST(root, k):2low <- [], high <- []3node1 <- root, node2 <- root4WHILE true:5 WHILE node1 != null: PUSH node1 TO low; node1 <- node1.left6 WHILE node2 != null: PUSH node2 TO high; node2 <- node2.right7 left <- TOP(low), right <- TOP(high)8 IF left = right: RETURN false9 IF left.val + right.val = k: RETURN true10 ELSE IF left.val + right.val < k: node1 <- POP(low).right11 ELSE: node2 <- POP(high).left
← / → step · space play · Home restart