## Algorithm

Problem Name: Data Structures - Binary Search Tree : Lowest Common Ancestor

In this HackerRank in Data Structures - Binary Search Tree : Lowest Common Ancestor solutions

You are given pointer to the root of the binary search tree and two values v1 and v2. You need to return the lowest common ancestor (LCA) of v1 and v2 in the binary search tree.
In the diagram above, the lowest common ancestor of the nodes 4 and 6 is the node 3. Node 3 is the lowest node which has nodes 4 and 6 as descendants.

Function Description

Complete the function lca in the editor below. It should return a pointer to the lowest common ancestor node of the two values given.

lca has the following parameters:
- root: a pointer to the root node of a binary search tree
- v1: a node.data value
- v2: a node.data value

Input Format

The first line contains an integer, n, the number of nodes in the tree.
The second line contains n space-separated integers representing node.data values.
The third line contains two space-separated integers, v1 and v2.

To use the test data, you will have to create the binary search tree yourself. Here on the platform, the tree will be created for you.

Constraints

1 <= n,node.data <= 25

1 <= v1,v2 <= 25

v1 not= v2

The tree will contain nodes with data equal to v1 and v2.

Output Format

Return the a pointer to the node that is the lowest common ancestor of v1 and v2.

Sample Input

6
4 2 3 1 7 6
1 7


v1 = 1 and v2 = 7

Sample Output

[reference to node 4]

Explanation

LCA of 1 and 7 is 4, the root in this case.
Return a pointer to the node.

## Code Examples

### #1 Code Example with C Programming

Code - C Programming


#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

struct node {

int data;
struct node *left;
struct node *right;

};

struct node* insert( struct node* root, int data ) {

if(root == NULL) {

struct node* node = (struct node*)malloc(sizeof(struct node));

node->data = data;

node->left = NULL;
node->right = NULL;
return node;

} else {

struct node* cur;

if(data  < = root->data) {
cur = insert(root->left, data);
root->left = cur;
} else {
cur = insert(root->right, data);
root->right = cur;
}

return root;
}
}

/* you only have to complete the function given below.
node is defined as

struct node {

int data;
struct node *left;
struct node *right;

};

*/
struct node *lca( struct node *root, int v1, int v2 ) {

while(root!= NULL){
if(v1 > root->data && v2 > root->data){
root = root->right;
}else if(v1  <  root->data && v2 <  root->data){
root = root ->left;
}else{
break;
}
}
return root;
}

int main() {

struct node* root = NULL;

int t;
int data;

scanf("%d", &t);

while(t-- > 0) {
scanf("%d", &data);
root = insert(root, data);
}
int v1;
int v2;

scanf("%d%d", &v1, &v2);
struct node *ans = lca(root, v1, v2);
printf("%d", ans->data);

return 0;
}


Copy The Code &

### #2 Code Example with C++ Programming

Code - C++ Programming


#include <bits/stdc++.h>

using namespace std;

class Node {
public:
int data;
Node *left;
Node *right;
Node(int d) {
data = d;
left = NULL;
right = NULL;
}
};

class Solution {
public:
Node* insert(Node* root, int data) {
if(root == NULL) {
return new Node(data);
} else {
Node* cur;
if(data  < = root->data) {
cur = insert(root->left, data);
root->left = cur;
} else {
cur = insert(root->right, data);
root->right = cur;
}

return root;
}
}

/*The tree node has data, left child and right child
class Node {
int data;
Node* left;
Node* right;
};

*/
/*
Node is defined as

typedef struct node
{
int data;
node * left;
node * right;
}node;

*/

Node * lca(Node * root, int v1,int v2)
{
if(root == nullptr) return nullptr;
int data = root->data;
if(v1 < data && v2  <  data> return lca(root->left, v1, v2);
if(v1 > data && v2 > data) return lca(root->right, v1, v2);
return root;
}

}; //End of Solution

int main() {

Solution myTree;
Node* root = NULL;

int t;
int data;

std::cin >> t;

while(t-- > 0) {
std::cin >> data;
root = myTree.insert(root, data);
}

int v1, v2;
std::cin >> v1 >> v2;

Node *ans = myTree.lca(root, v1, v2);

std::cout << ans->data;

return 0;
}

Copy The Code &

### #3 Code Example with Java Programming

Code - Java Programming


import java.util.*;
import java.io.*;

class Node {
Node left;
Node right;
int data;

Node(int data) {
this.data = data;
left = null;
right = null;
}
}

class Solution {

/*
class Node
int data;
Node left;
Node right;
*/

/*
class Node
int data;
Node left;
Node right;
*/
static Node lca(Node root,int v1,int v2)
{
//Decide if you have to call rekursively
//Samller than both
if(root.data < v1 && root.data  <  v2){
return lca(root.right,v1,v2>;
}
//Bigger than both
if(root.data > v1 && root.data > v2){
return lca(root.left,v1,v2);
}

//Else solution already found
return root;
}

public static Node insert(Node root, int data) {
if(root == null) {
return new Node(data);
} else {
Node cur;
if(data <= root.data) {
cur = insert(root.left, data);
root.left = cur;
} else {
cur = insert(root.right, data);
root.right = cur;
}
return root;
}
}

public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int t = scan.nextInt(>;
Node root = null;
while(t-- > 0) {
int data = scan.nextInt();
root = insert(root, data);
}
int v1 = scan.nextInt();
int v2 = scan.nextInt();
scan.close();
Node ans = lca(root,v1,v2);
System.out.println(ans.data);
}
}

Copy The Code &

### #4 Code Example with Python Programming

Code - Python Programming


class Node:
def __init__(self, info):
self.info = info
self.left = None
self.right = None
self.level = None

def __str__(self):
return str(self.info)

class BinarySearchTree:
def __init__(self):
self.root = None

def create(self, val):
if self.root == None:
self.root = Node(val)
else:
current = self.root

while True:
if val < current.info:
if current.left:
current = current.left
else:
current.left = Node(val)
break
elif val > current.info:
if current.right:
current = current.right
else:
current.right = Node(val)
break
else:
break

# Enter your code here. Read input from STDIN. Print output to STDOUT
'''
class Node:
def __init__(self,info):
self.info = info
self.left = None
self.right = None

// this is a node of the tree , which contains info as data, left , right
'''

def lca(root, v1, v2):
if (root.info < v1 and root.info > v2) or (root.info > v1 and root.info < v2):
return root
elif root.info < v1 and root.info < v2:
return lca(root.right, v1, v2)
elif root.info > v1 and root.info > v2:
return lca(root.left, v1, v2)
elif root.info == v1 or root.info == v2:
return root

tree = BinarySearchTree()
t = int(input())

arr = list(map(int, input().split()))

for i in range(t):
tree.create(arr[i])

v = list(map(int, input().split()))

ans = lca(tree.root, v[0], v[1])
print (ans.info)

Copy The Code &