// Find the closest matching number from a binary search tree
#include <iostream>
#include <cassert>
using namespace std;
template <typename T>
class BST {
struct treeNode;
struct treeNode {
treeNode(const T& val) : val(val), left(0), right(0) {}
T val;
struct treeNode *left;
struct treeNode *right;
};
public:
BST() : root(0) {}
~BST() { clean_(root); }
void insert(const T& val) {
treeNode *t = root;
if(0 == root) root = new treeNode(val);
else while(t){
if(val < t->val) {
if(t->left) t = t->left;
else t->left = new treeNode(val), t = 0;
} else {
if(t->right) t = t->right;
else t->right = new treeNode(val), t = 0;
}
}
}
bool find(const T& val) {
treeNode *t = root;
while(t){
if(val == t->val) return true;
if(val < t->val) t = t->left;
else t = t->right;
}
return false;
}
T find_closest(const T& val) {
const T v1( smallestEleGreaterThanVal(root, val) );
const T v2( LargestEleSmallerThanVal(root, val) );
return v1-val < val-v2 ? v1 : v2;
}
void debug_traverse() {
if(root) debug_traverse(root);
}
private:
T smallestEleGreaterThanVal(treeNode *t, T val) {
T r = 9999; // FIXME:: Replace with T.infinity() or root
while(t) {
if(t->val == val) return val;
if(t->val < val) return min(r, smallestEleGreaterThanVal(t->right, val));
else r = t->val, t = t->left;
}
return r;
}
T LargestEleSmallerThanVal(treeNode *t, T val) {
T r = -9999; // FIXME:: Replace with -T.infinity() or root
while(t) {
if(t->val == val) return val;
if(t->val > val) return max(r, LargestEleSmallerThanVal(t->left, val));
else r = t->val, t = t->right;
}
return r;
}
void debug_traverse(treeNode *t) {
if(t->left) debug_traverse(t->left);
cout << t->val << ' ';
if(t->right) debug_traverse(t->right);
}
void clean_(treeNode *p) {
if(p) {
if(p->left) clean_(p->left);
if(p->right) clean_(p->right);
}
delete p;
}
private:
treeNode *root;
};
int main() {
BST<int> b;
b.insert(15);
b.insert(8);
b.insert(45);
b.insert(12);
b.insert(65);
b.insert(38);
b.insert(1);
b.insert(10);
b.insert(4);
b.insert(64);
cout << "Tree contents are: ";
b.debug_traverse();
cout << endl;
assert( b.find(12) );
assert( !b.find(13) );
cout << "Content nearest to -5 is " << b.find_closest(-5) << endl;
cout << "Content nearest to 7 is " << b.find_closest(7) << endl;
cout << "Content nearest to 8 is " << b.find_closest(8) << endl;
cout << "Content nearest to 9 is " << b.find_closest(9) << endl;
cout << "Content nearest to 13 is " << b.find_closest(13) << endl;
cout << "Content nearest to 100 is " << b.find_closest(100) << endl;
return 0;
}
// Q: What is the practical usage of a function like find_closest?
// A: It can find best matching floating point number from a tree
// of floats or doubles in O(log N) time.