Given the values of two nodes in a *binary search tree*, write a c program to find the lowest common ancestor. You may assume that both values already exist in the tree.

The function prototype is as follows:

` int FindLowestCommonAncestor(node* root, int value1, int value)`

` I/P : 4 and 14`

` O/P : 8`

` (Here the common ancestors of 4 and 14, are {8,20}.`

` Of {8,20}, the lowest one is 8).`

**Algorithm:**

The main idea of the solution is — While traversing Binary Search Tree from top to bottom, the first node n we encounter with value between n1 and n2, i.e., n1 < n < n2 is the Lowest or Least Common Ancestor(LCA) of n1 and n2 (where n1 < n2). So just traverse the BST in pre-order, if you find a node with value in between n1 and n2 then n is the LCA, if it’s value is greater than both n1 and n2 then our LCA lies on left side of the node, if it’s value is smaller than both n1 and n2 then LCA lies on right side.

**Implementation:**

`#include <stdio.h>` `#include <stdlib.h>` `/* A binary tree node has data, pointer to left child` ` and a pointer to right child */` `struct` `node` `{` ` int` `data;` ` struct` `node* left;` ` struct` `node* right;` `};` `struct` `node* newNode(int` `);` `/* Function to find least comman ancestor of n1 and n2 */` `int` `leastCommanAncestor(struct` `node* root, int` `n1, int` `n2)` `{` ` /* If we have reached a leaf node then LCA doesn't exist ` ` If root->data is equal to any of the inputs then input is ` ` not valid. For example 20, 22 in the given figure */` ` if(root == NULL || root->data == n1 || root->data == n2)` ` return` `-1; ` ` ` ` /* If any of the input nodes is child of the current node` ` we have reached the LCA. For example, in the above figure` ` if we want to calculate LCA of 12 and 14, recursion should ` ` terminate when we reach 8*/` ` if((root->right != NULL) && ` ` (root->right->data == n1 || root->right->data == n2))` ` return` `root->data;` ` if((root->left != NULL) && ` ` (root->left->data == n1 || root->left->data == n2))` ` return` `root->data; ` ` ` ` if(root->data > n1 && root->data < n2)` ` return` `root->data;` ` if(root->data > n1 && root->data > n2)` ` return` `leastCommanAncestor(root->left, n1, n2);` ` if(root->data < n1 && root->data < n2)` ` return` `leastCommanAncestor(root->right, n1, n2);` `} ` `/* Helper function that allocates a new node with the` ` given data and NULL left and right pointers. */` `struct` `node* newNode(int` `data)` `{` ` struct` `node* node = (struct` `node*)` ` malloc(sizeof(struct` `node));` ` node->data = data;` ` node->left = NULL;` ` node->right = NULL;` ` return(node);` `}` `/* Driver program to test mirror() */` `int` `main()` `{` ` struct` `node *root = newNode(2);` ` root->left = newNode(1);` ` root->right = newNode(4);` ` root->right->left = newNode(3);` ` root->right->right = newNode(5); ` `/* Constructed binary search tree is` ` 2` ` / \` ` 1 4` ` / \` ` 3 5` `*/` ` printf("\n The Least Common Ancestor is \n");` ` printf("%d", leastCommanAncestor(root, 3, 5));` ` getchar();` ` return` `0;` `}` |

Note that above function assumes that n1 is smaller than n2.

**Time complexity:**Time complexity is O(Logn) for a balanced BST and O(n) for a skewed BST.

__Please Leave comment if you have doubts. Give ur solution thru comments.__

__Concat me through mail id:__**poratltechinfo@gmail.com**

## Leave a Reply