CODEWITHSUNDEEP
algorithmbinary-search-tree
Kamal
Kamal

Reputation: 630

Finding the k closest numbers to a target number in a binary search tree

I encountered the following leetcode question and I had a question about the approach some people used to solve it. The question is: Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

Note: Given target value is a floating point.

You may assume k is always valid, that is: k ≤ total nodes.

You are guaranteed to have only one unique set of k values in the BST that are closest to the target.

So, what some people did is that they did an in order traversal while maintaining a k sized queue of the closest elements. During the in order traversal, if they find an element that is closer to the target than the first node in the queue, they remove the first node from the queue and add in the current value. My question is, why do they compare with the first element in the queue? Here is some code for what I am referring to: https://leetcode.com/discuss/94472/inorder-one-linkedlist-java-solution-beat-85%25

Upvotes: 3

Views: 4812

Answers (2)

Gene
Gene

Reputation: 46990

The in-order traversal will find all the elements less than or equal to the target first. As it approaches, new, ever-closer elements are added to the tail of the list in sorted order. After it reaches length k, adding a new closer element at the tail requires deleting one farther away. The farthest away is the head, so it deletes that.

After the search passes the target, it starts seeing elements ever-farther away from it. The question as each is considered is whether it's closer to the target than the ones already in the list. Suppose k=5 the list looks like this:

a <= b <= c <= d <= e (<= x?)
             ^
             Target value somewhere between c and d

And the next value x >= e has just been discovered by the search. There are only two possibilities:

  1. x is closer to the target than a. In this case we want to delete a and add x at the tail.

  2. x is farther away from the target than a. In this case, we let the list alone. In addition, we can be sure that every further in-order element will be yet farther away from the target, so the search can be cut short.

Happily, the test needed to make this choice after passing the target is always satisfied before the target is reached, so the same code suffices in both cases.

This is an elegant solution, but it has O(n) run time for a tree of n elements.

A more complex but asymptotically faster solution relies on tree iterators. It's possible to build iterators that can be initialized in O(h) time to start at any element where h is the height of the tree. Initialize two of these at the target, then move one left and the other right, always choosing the closest to the target to move next. Stop when k elements have been found. Advancing these iterators has the same time complexity as each step of an in-order traversal: amortized constant time. So the whole algorithm is O(h + k). If the tree is balanced, this is O(log n + k), which is much better when k << n.

Upvotes: 6

Scott Hunter
Scott Hunter

Reputation: 49893

Presumably, the first node in the queue is the farthest from the target of the elements in the queue, and the queue would only need to change if something closer than that was found.

Upvotes: 1

Related Questions