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

Tree contents are: 1 4 8 10 12 15 38 45 64 65 
Content nearest to -5 is 1
Content nearest to 7 is 8
Content nearest to 8 is 8
Content nearest to 9 is 8
Content nearest to 13 is 12
Content nearest to 100 is 65