Two Sum IV - Input is a BST
Easy · Trees · Hash Table · Two Pointers · Tree · Binary Search Tree · Binary Tree
Problem
Given the root of a binary search tree and an integer k, return True if two different nodes in the tree have values that add up to k, and False otherwise. A node cannot be paired with itself.
In a binary search tree, every value in a node's left subtree is smaller than the node's value and every value in its right subtree is larger, so an in-order walk lists the values sorted.
The tree is given in level order, with None for a missing child. from_level([6,3,9,1,4,None,12]) builds it and to_level(root) turns it back into a list.
Examples
Input: root = [6,3,9,1,4,None,12], k = 13 Output: True
1 + 12 = 13 (and 4 + 9 = 13).
Input: root = [6,3,9,1,4,None,12], k = 8 Output: False
4 + 4 = 8 would use the same node twice, and no two different values add up to 8.
Input: root = [5], k = 10 Output: False
There is only one node, so there is no pair at all.
Constraints
- 1 <= number of nodes <= 10^4
- -10^4 <= Node.val <= 10^4
- root is a valid binary search tree (values are distinct)
- -10^5 <= k <= 10^5
Approaches
- Check every pair of nodes — time O(n²), space O(n)
Follow-up
Can you avoid copying the values into a list? Two iterators over the tree, one walking in order from the smallest and one in reverse from the largest, each with its own stack, give two pointers in O(h) space.
Related problems
Start free on Cariara · Coding problems · System design studio
