Finding two nodes in a tree that add up to a value

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


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