CODEWITHSUNDEEP
algorithmsearchdata-structurestree
JoJo
JoJo

Reputation: 1447

Given a binary search tree and a key, How to find first M tree nodes which values are closest to that key?

Recently, I encounter an algorithm problem:

Given a binary search tree and a key, How to find first M tree nodes which values are closest to that key?

My idea is to use In-order traversal to put each tree node value into a another array. And we then use binary search to find the most closest node X to that given key in this array. In the end, we start search from this node X to the left and right side to find the first M values are closest to that given key.

However, My idea require O(n) time and O(n) space. is there some better thought than my idea?

Upvotes: 0

Views: 136

Answers (1)

Scott Hunter
Scott Hunter

Reputation: 49893

  1. Locate the key (or at least where it would go)
  2. From that point, advance to the next highest value
  3. Also from that point, regress to the next lowest value
  4. Whichever is closer, save that value and move to the next value away from the key. That is, if the higher value is closer, go to the next higher value; otherwise, go to the next lower one.
  5. Continue until you have your M nodes.

Upvotes: 0

Related Questions