How to find the closest element to a given key value in a binary search tree?

algorithm data-structures binary-search-tree
phoenix picture phoenix · Jun 2, 2011 · Viewed 32k times · Source

Given a bst with integer values as keys how do I find the closest node to that key in a bst ? The BST is represented using a object of nodes (Java). Closest will be for eg 4,5,9 and if the key is 6 it will return 5 ..

Answer

x4u picture x4u · Jun 2, 2011

Traverse the tree as you would to find the element. While you do that record the value that is closest to your key. Now when you didn't find a node for the key itself return the recorded value.

So if you were looking for the key 3 in the following tree you would end up on the node 6 without finding a match but your recorded value would be 2 since this was the closest key of all nodes that you had traversed (2,7,6).

                 2
              1      7
                   6   8

Related questions

How do you validate a binary search tree?

I read on here of an exercise in interviews known as validating a binary search tree. How exactly does this work? What would one be looking for in validating a binary search tree? I have written a basic search tree, …

Read More
Pre-order to post-order traversal

If the pre-order traversal of a binary search tree is 6, 2, 1, 4, 3, 7, 10, 9, 11, how to get the post-order traversal?

Read More
In Order Successor in Binary Search Tree

Given a node in a BST, how does one find the next higher key?

Read More