Two values that add up
Decide whether two different nodes of a search tree add up to a target, by reading the values in sorted order with an inorder walk and closing in from both ends. About 14 minutes.
Inorder is sorted
Visiting a search tree in inorder order, left subtree, node, right subtree, gives the values from smallest to largest. That is the defining feature of a search tree, and it turns the tree into a sorted list.
So collect the values with an inorder walk into a list. Everything you know about sorted lists is now available.
def walk(node):
if node is None:
return
walk(node.left)
vals.append(node.val)
walk(node.right)2 + 7 = 9 is below 11. Move the left pointer up.
Close in from both ends
Put one pointer at the smallest value and one at the largest. Add the two values. If the sum is the target, you are done. If it is too small, the smallest value cannot be part of any pair with a bigger partner than the current one, so move the left pointer up. If it is too big, move the right pointer down.
Stop when the pointers meet. A value cannot pair with itself, so the pointers must stay apart.
s = vals[i] + vals[j]
if s < k:
i += 1
else:
j -= 1The two pointers add to more than the target. Which one moves?
- AThe right pointer moves down to a smaller value
- BThe left pointer moves up
- CBoth move
Show the answer
The right pointer moves down to a smaller value. The right value is the largest in range, so lowering it is the way to reduce the sum.
Two sum in a search tree
Given the root of a binary search tree with different values and an integer k, return true if there exist two different nodes in the tree whose values add up to k.
root = [5, 3, 6, 2, 4, null, 7], k = 9 → true
0 ≤ number of nodes ≤ 10,000 · -10,000 ≤ node.val ≤ 10,000 · -20,000 ≤ k ≤ 20,000