DSA problem
Two Sum IV - Input is a BST
Given the root of a binary search tree and an integer k, return true if there exist two distinct nodes in the BST whose values sum to k, and false otherwise.
The classic Two Sum on an array uses a hash set to remember complements seen so far. The same idea transfers directly to trees: traverse the BST in any order, and for each visited node check whether k - node.val is already in a hash set; if it is, return true, otherwise add node.val and continue. This runs in O(n) time and O(n) space.
The BST structure invites a more memory-efficient alternative based on inorder traversal. An inorder walk yields values in sorted order, so once you produce that sequence you can apply the two-pointer Two Sum trick on a sorted array. Producing the list is O(n) time and O(n) space; with a BST iterator you can simulate the two pointers using only O(h) auxiliary space.
The optimal trick uses two BST iterators in opposite directions — one yielding values in ascending order (next) and one in descending order (prev). At each step compare lo + hi to k: if equal return true, if smaller advance the ascending iterator, if larger advance the descending iterator. This runs in O(n) time with O(h) extra space.
Examples
root = [5,3,6,2,4,null,7], k = 9trueroot = [5,3,6,2,4,null,7], k = 28falseroot = [2,1,3], k = 4trueConstraints
- The number of nodes in the tree is in the range [1, 10^4].
- -10^4 <= Node.val <= 10^4
- root is guaranteed to be a valid BST.
- -10^5 <= k <= 10^5
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.