// program to find the common ancestor of nodes in binary search tree
#include<iostream>

using namespace std;

class node{
	protected:
		int element;
		node* left;
		node* right;
		
	public:
		
		//constructor that accepts only element
		node(int element){
			this->element = element;
			this->left = NULL;
			this->right = NULL;
		}
		
		//constructor that accepts element, left Link, Right Link
		node(int element, node* leftLink, node* rightLink){
			this->element = element;
			this->left = leftLink;
			this->right = rightLink;
		}

		//method to update data of the node
		void updateData(int element){
			this->element = element;
		}

		//method to update the left Link of the node
		void updateLeftLink(node* temp){
			this->left = temp;
		}

		//method to update the right link of the node
		void updateRightLink(node* temp){
			this->right = temp;
		}
	
		//method that returns the element of the node
		int getElement(){
			return this->element;
		}

		//method that returns left Link
		node* getLeftNode(){
			return this->left;
		}

		//method that returns the right Link
		node* getRightNode(){
			return this->right;
		}
};

//binary search tree class
class BST{
	protected:
		node* root;
		
	public:
		
		//constructor for bst
		BST(){
			root = NULL;
		}

		//returns true if the root node is null
		bool isEmpty(){
			return(root == NULL);
		}
		
		//returns root node
		node* getRoot(){
			return root;
		}
		
		void insert(int element){			
			node* temp = new node(element);
			//if tree is empty put it at root node
			if(root == NULL){
				root = temp;
			}
			else{
				bool inserted = false;
				//creating a node pointer to traverse the tree
				node* p = root;

				//keep looping while the node is not inserted
				while(not inserted){
					//if element of the new node is less than the current node than insert it to the left
					if(p->getElement() > temp->getElement()){
						if(p->getLeftNode() == NULL){
							p->updateLeftLink(temp);
							inserted = true;
						}
						else{
							p = p->getLeftNode();
						}
					}
					//if element of the new node is greater than the current node than insert it to the right
					else if(p->getElement() < temp->getElement()){
						if(p->getRightNode() == NULL){
							p->updateRightLink(temp);
							inserted = true;
						}
						else{
							p = p->getRightNode();
						}
					}
				}
			}
		}

		// method to find the common ancestor of 2 data elements
        // both the elements passed to the method must be present in the BST
		void commonAncestor(node* n, int e1, int e2){
			
			int data = n->getElement();
			static bool printParent = false;
			// if both are greater than the node data then traverse right 
			if(data < e1 && data < e2){
				commonAncestor(n->getRightNode(),e1,e2);
			}
			
			// if both are less than node data then traverse left
			else if(data > e1 && data > e2){
				commonAncestor(n->getLeftNode(),e1,e2);
			}

            // if any element is equal to data then the parent element is the common ancestor
            else if(data == e1 || data == e2){
                printParent = true;
                return;
            }
			// if both above cases are not satisfied then the current node is the common ancestor node
			else{
				cout<<"\n\nThe Local common ancestor for "<<e1<<" and "<<e2<<" is : "<<n->getElement();
                return;
			}

            if(printParent == true){
                cout<<"\n\nThe Local common ancestor for "<<e1<<" and "<<e2<<" is : "<<n->getElement();
                // reset static printParent variable
                printParent = false;
            }
			
		}
		
};

int main()
{
    BST b1;
    b1.insert(7);
    b1.insert(29);
    b1.insert(25);
    b1.insert(36);
    b1.insert(71);
    b1.insert(24);
    b1.insert(5);
    b1.insert(9);
    b1.insert(1);

    node* root = b1.getRoot();
    cout<<"The Root element of the BST is : "<<root->getElement()<<endl;

    b1.commonAncestor(root,24,5);
    b1.commonAncestor(root,1,5);
    b1.commonAncestor(root,25,36);

}