//15 Find LowestCommon Anscestor in a Binary Search Tree
// In BST: left <= self <= right
//2011-06-18
#include <iostream>
using namespace std;
struct node{
int data;
node *left;
node *right;
};
int level_cutoff = 3;
node *createNode(int value){
node *n = new node;
if (!n) return NULL;
n->left = NULL;
n->right = NULL;
//cout << counter <<"\n";
n->data = value;
return n;
}
void addChildren(node *n, int level, int value){
if (level >= level_cutoff) return;
int difference = (2 << (level_cutoff - level - 1))/2;
node *l = createNode(value-difference);
if(l) {
n->left = l;
}
node *r = createNode(value+difference);
if(r) {
n->right = r;
}
addChildren(l, level+1, value-difference);
addChildren(r, level+1, value+difference);
}
void printTree(node *n, int level){
if(!n) return;
cout.width(level*4); cout.fill(' ');
cout << n->data << "\n" ;
printTree(n->left, level+1);
printTree(n->right, level+1);
}
int FindLowestCommonAncestor(node *root, int v1, int v2){
node *cursor = root;
while(cursor){
int v = cursor->data;
if (v1 < v && v2 < v ) cursor = cursor->left;
else if (v1 > v && v2 > v ) cursor = cursor->right;
else return v;
}
return 0;
}
int main(){
int root_v = (2 << (level_cutoff-1))-1;
node *root = createNode( root_v);
addChildren(root,0,root_v);
cout << "\nBinary Search Tree is \n";
printTree(root,0);
int v1 = 8, v2 = 13;
cout << "\nLowest common ancestor of " << v1 << " and " << v2 << " is ";
cout << FindLowestCommonAncestor(root, v1,v2) << "\n";
return 1;
}