[ create a new paste ] login | about

Link: http://codepad.org/jOA5JmUC    [ raw code | output | fork ]

baojie - C++, pasted on Jun 19:
//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;
}


Output:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Binary Search Tree is 
7
   3
       1
           0
           2
       5
           4
           6
  11
       9
           8
          10
      13
          12
          14

Lowest common ancestor of 8 and 13 is 11


Create a new paste based on this one


Comments: