jain12

find least common ancestor in a binary tree(2)

Mar 31st, 2020
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.83 KB | None | 0 0
  1. #include<iostream>
  2. #include<vector>
  3. using namespace std;
  4.  
  5. class Node{
  6.   public:
  7.       int data;
  8.       Node *left,*right;
  9.       Node(int key){
  10.         data=key;
  11.         left=NULL;
  12.         right=NULL;
  13.         }
  14.   };
  15.  
  16. Node* FindLCA(Node *root,int key1,int key2){
  17.  if(root==NULL)
  18.    return NULL;
  19.  if(root->data==key1 || root->data==key2)
  20.     return root;
  21.  Node* left=FindLCA(root->left,key1,key2);
  22.  Node* right=FindLCA(root->right,key1,key2);
  23.  if(left!=NULL && right!=NULL)
  24.     return root;
  25.  else
  26.     return left!=NULL? left:right;
  27.   }
  28.  
  29. int main(){
  30.   Node* root=NULL;
  31.   Node* newnode=new Node(1);
  32.   root=newnode;
  33.   root->left=new Node(9);
  34.   root->right=new Node(3);
  35.   (root->left)->left=new Node(2);
  36.   (root->right)->right=new Node(4);
  37.   Node* temp=FindLCA(root,1,3);
  38.   cout<<" "<<temp->data;
  39.   return 0;
  40.   }
Add Comment
Please, Sign In to add comment