fork download
copy 
  1. //
  2. //  main.cpp
  3. //  Lowest Common Ancestor (LCA)
  4. //
  5. //  Created by Himanshu on 31/10/21.
  6. //
  7.  
  8. #include <iostream>
  9. #include <queue>
  10. using namespace std;
  11.  
  12. struct node {
  13.     int info = 0;
  14.     struct node *left, *right;
  15. };
  16. typedef struct node Node;
  17.  
  18. node* newNode(int data)
  19. {
  20.     node* Node = new node();
  21.     Node->info = data;
  22.     Node->left = NULL;
  23.     Node->right = NULL;
  24.  
  25.     return(Node);
  26. }
  27.  
  28.  
  29. Node* lca (Node *root, int n1, int n2) {
  30.     if (root == NULL) {
  31.         return NULL;
  32.     }
  33.  
  34.     if (root->info == n1 || root->info == n2) {
  35.         return root;
  36.     }
  37.  
  38.     Node *leftLCA  = lca(root->left, n1, n2);
  39.     Node *rightLCA = lca(root->right, n1, n2);
  40.  
  41.     if (leftLCA && rightLCA) {
  42.         return root;
  43.     }
  44.  
  45.     return (leftLCA != NULL)? leftLCA : rightLCA;
  46. }
  47.  
  48.  
  49. int main() {
  50.     Node *root = newNode(1);
  51.     root->left = newNode(20);
  52.     root->right = newNode(21);
  53.     root->right->left = newNode(30);
  54.     root->right->right = newNode(31);
  55.     root->right->right->left = newNode(40);
  56.     root->right->right->left->right = newNode(51);
  57.  
  58.     Node *key = NULL;
  59.  
  60.     cout<<"The lowest common ancestors of 20 amd 30 are: "<<endl;
  61.     key = lca(root, 20, 30);
  62.     cout<<(key->info);
  63.     cout<<endl;
  64.  
  65.     cout<<"The lowest common ancestors of 40 amd 51 are: "<<endl;
  66.     key = lca(root, 40, 51);
  67.     cout<<(key->info);
  68.     cout<<endl;
  69.  
  70.     return 0;
  71. }
  72.  
Success #stdin #stdout 0.01s 5436KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
The lowest common ancestors of 20 amd 30 are: 
1
The lowest common ancestors of 40 amd 51 are: 
40
https://ideone.com/DjhEmS
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!