document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. // program to find the common ancestor of nodes in binary search tree
  2. #include<iostream>
  3.  
  4. using namespace std;
  5.  
  6. class node{
  7.     protected:
  8.         int element;
  9.         node* left;
  10.         node* right;
  11.        
  12.     public:
  13.        
  14.         //constructor that accepts only element
  15.         node(int element){
  16.             this->element = element;
  17.             this->left = NULL;
  18.             this->right = NULL;
  19.         }
  20.        
  21.         //constructor that accepts element, left Link, Right Link
  22.         node(int element, node* leftLink, node* rightLink){
  23.             this->element = element;
  24.             this->left = leftLink;
  25.             this->right = rightLink;
  26.         }
  27.  
  28.         //method to update data of the node
  29.         void updateData(int element){
  30.             this->element = element;
  31.         }
  32.  
  33.         //method to update the left Link of the node
  34.         void updateLeftLink(node* temp){
  35.             this->left = temp;
  36.         }
  37.  
  38.         //method to update the right link of the node
  39.         void updateRightLink(node* temp){
  40.             this->right = temp;
  41.         }
  42.    
  43.         //method that returns the element of the node
  44.         int getElement(){
  45.             return this->element;
  46.         }
  47.  
  48.         //method that returns left Link
  49.         node* getLeftNode(){
  50.             return this->left;
  51.         }
  52.  
  53.         //method that returns the right Link
  54.         node* getRightNode(){
  55.             return this->right;
  56.         }
  57. };
  58.  
  59. //binary search tree class
  60. class BST{
  61.     protected:
  62.         node* root;
  63.        
  64.     public:
  65.        
  66.         //constructor for bst
  67.         BST(){
  68.             root = NULL;
  69.         }
  70.  
  71.         //returns true if the root node is null
  72.         bool isEmpty(){
  73.             return(root == NULL);
  74.         }
  75.        
  76.         //returns root node
  77.         node* getRoot(){
  78.             return root;
  79.         }
  80.        
  81.         void insert(int element){          
  82.             node* temp = new node(element);
  83.             //if tree is empty put it at root node
  84.             if(root == NULL){
  85.                 root = temp;
  86.             }
  87.             else{
  88.                 bool inserted = false;
  89.                 //creating a node pointer to traverse the tree
  90.                 node* p = root;
  91.  
  92.                 //keep looping while the node is not inserted
  93.                 while(not inserted){
  94.                     //if element of the new node is less than the current node than insert it to the left
  95.                     if(p->getElement() > temp->getElement()){
  96.                         if(p->getLeftNode() == NULL){
  97.                             p->updateLeftLink(temp);
  98.                             inserted = true;
  99.                         }
  100.                         else{
  101.                             p = p->getLeftNode();
  102.                         }
  103.                     }
  104.                     //if element of the new node is greater than the current node than insert it to the right
  105.                     else if(p->getElement() < temp->getElement()){
  106.                         if(p->getRightNode() == NULL){
  107.                             p->updateRightLink(temp);
  108.                             inserted = true;
  109.                         }
  110.                         else{
  111.                             p = p->getRightNode();
  112.                         }
  113.                     }
  114.                 }
  115.             }
  116.         }
  117.  
  118.         // method to find the common ancestor of 2 data elements
  119.         // both the elements passed to the method must be present in the BST
  120.         void commonAncestor(node* n, int e1, int e2){
  121.            
  122.             int data = n->getElement();
  123.             static bool printParent = false;
  124.             // if both are greater than the node data then traverse right
  125.             if(data < e1 && data < e2){
  126.                 commonAncestor(n->getRightNode(),e1,e2);
  127.             }
  128.            
  129.             // if both are less than node data then traverse left
  130.             else if(data > e1 && data > e2){
  131.                 commonAncestor(n->getLeftNode(),e1,e2);
  132.             }
  133.  
  134.             // if any element is equal to data then the parent element is the common ancestor
  135.             else if(data == e1 || data == e2){
  136.                 printParent = true;
  137.                 return;
  138.             }
  139.             // if both above cases are not satisfied then the current node is the common ancestor node
  140.             else{
  141.                 cout<<"\\n\\nThe Local common ancestor for "<<e1<<" and "<<e2<<" is : "<<n->getElement();
  142.                 return;
  143.             }
  144.  
  145.             if(printParent == true){
  146.                 cout<<"\\n\\nThe Local common ancestor for "<<e1<<" and "<<e2<<" is : "<<n->getElement();
  147.                 // reset static printParent variable
  148.                 printParent = false;
  149.             }
  150.            
  151.         }
  152.        
  153. };
  154.  
  155. int main()
  156. {
  157.     BST b1;
  158.     b1.insert(7);
  159.     b1.insert(29);
  160.     b1.insert(25);
  161.     b1.insert(36);
  162.     b1.insert(71);
  163.     b1.insert(24);
  164.     b1.insert(5);
  165.     b1.insert(9);
  166.     b1.insert(1);
  167.  
  168.     node* root = b1.getRoot();
  169.     cout<<"The Root element of the BST is : "<<root->getElement()<<endl;
  170.  
  171.     b1.commonAncestor(root,24,5);
  172.     b1.commonAncestor(root,1,5);
  173.     b1.commonAncestor(root,25,36);
  174.  
  175. }
');