fork(43) download
copy 
  1. // An iterative C program to find LCA of two nodes n1 and n2.
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4.  
  5. struct node
  6. {
  7.     int data;
  8.     struct node* left, *right;
  9. };
  10.  
  11. /* Function to find LCA of n1 and n2. The function assumes that both
  12.    n1 and n2 are present in BST */
  13. struct node *lca(struct node* root, int n1, int n2)
  14. {
  15.     while (root != NULL)
  16.     {
  17.          // If both n1 and n2 are greater than root, then LCA lies in left
  18.         if (root->data > n1 && root->data > n2)
  19.            root = root->left;
  20.  
  21.         // If both n1 and n2 are smaller than root, then LCA lies in right
  22.         else if (root->data < n1 && root->data < n2)
  23.            root = root->right;
  24.  
  25.         else break;
  26.     }
  27.     return root;
  28. }
  29.  
  30. /* Helper function that allocates a new node with the given data.*/
  31. struct node* newNode(int data)
  32. {
  33.     struct node* node = (struct node*)malloc(sizeof(struct node));
  34.     node->data  = data;
  35.     node->left  = node->right = NULL;
  36.     return(node);
  37. }
  38.  
  39. /* Driver program to test mirror() */
  40. int main()
  41. {
  42.     // Let us construct the BST shown in the above figure
  43.     struct node *root        = newNode(20);
  44.     root->left               = newNode(8);
  45.     root->right              = newNode(22);
  46.     root->left->left         = newNode(4);
  47.     root->left->right        = newNode(12);
  48.     root->left->right->left  = newNode(10);
  49.     root->left->right->right = newNode(14);
  50.  
  51.     int n1 = 10, n2 = 14;
  52.     struct node *t = lca(root, n1, n2);
  53.     printf("LCA of %d and %d is %d \n", n1, n2, t->data);
  54.  
  55.     n1 = 14, n2 = 8;
  56.     t = lca(root, n1, n2);
  57.     printf("LCA of %d and %d is %d \n", n1, n2, t->data);
  58.  
  59.     n1 = 10, n2 = 22;
  60.     t = lca(root, n1, n2);
  61.     printf("LCA of %d and %d is %d \n", n1, n2, t->data);
  62.  
  63.     getchar();
  64.     return 0;
  65. }
  66.  
Success #stdin #stdout 0s 2428KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
LCA of 10 and 14 is 12 
LCA of 14 and 8 is 8 
LCA of 10 and 22 is 20
https://ideone.com/tL9aCD
language:
C (gcc 8.3)
created:
10 years ago
visibility:
public

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!