jain12

find least common ancestor in BST

Mar 31st, 2020
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.42 KB | None | 0 0
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. class Node{
  5.   public:
  6.       int data;
  7.       Node *left,*right;
  8.       Node(int key){
  9.         data=key;
  10.         left=right=NULL;
  11.         }
  12.   };
  13.  
  14. Node* FindLCA(Node* root,Node* first,Node* second ){
  15.   if(root==NULL)
  16.      return NULL;
  17.   if((min(first->data,second->data)<root->data && max(first->data,second->data)>root->data) ||first->data==root->data||second->data==root->data)
  18.      return root;
  19.   if(first->data<root->data )
  20.      return FindLCA(root->left,first,second);
  21.   if(first->data>root->data)
  22.      return FindLCA(root->right,first,second);
  23.    }
  24.  
  25. void Print(Node* root,int first,int last){
  26.   if(root==NULL)
  27.     return;
  28.   if(first<root->data)
  29.     Print(root->left,first,last);
  30.   if(root->data>=first && root->data<=last)
  31.     cout<<" "<<root->data;
  32.   if(root->data<last)
  33.     Print(root->right,first,last);
  34.   }
  35.  
  36. void Insert(Node **root_ref,int key){
  37.   if(*root_ref==NULL){
  38.     *root_ref=new Node(key);
  39.     return;
  40.     }
  41.   if((*root_ref)->data<key)
  42.     Insert(&((*root_ref)->right),key);
  43.   else
  44.      if((*root_ref)->data>key)
  45.        Insert(&((*root_ref)->left),key);
  46.   }
  47.  
  48. int main(){
  49.  Node *root=NULL;
  50.  Insert(&root,5);
  51.  Insert(&root,7);
  52.  Insert(&root,6);
  53.  Insert(&root,2);
  54.  Insert(&root,8);
  55.  Node* temp=FindLCA(root,(root->right)->left,(root->right)->right);
  56.  if(temp)
  57.     cout<<temp->data;
  58.  else
  59.     cout<<"values are not correct";
  60.  return 0;
  61.  }
Add Comment
Please, Sign In to add comment