Here is a variation of the problem that asks for two values that add up to an expected value
Given the root of a binary search tree, and a target K, return two nodes in the tree whose sum equals K.
Understanding the Problem
This is very similar to any problem that requires us to find two values that add up to a number. We simply need to keep track of all the numbers we have seen and simultaneously check to see if a number exists that satisfies our condition
Optimizing
Since this is a Binary Search Tree, we can optimize the search by only traversing certain branches of the tree.
Solving it
- Traverse the tree
- Build a set containing the values we have seen
- On each node, check if the "inverse" ie. ( sum - value ) exists in our set.
- If it does then the current value and the inverse is our solution
