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 ..
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