Binary Search Tree : Lowest Common Ancestor – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
1 Month Preparation Kit Solutions – HackerRank
C++ Binary Search Tree : Lowest Common Ancestor HackerRank Solution
#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;
}
Java Binary Search Tree : Lowest Common Ancestor HackerRank Solution
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);
}
}
Python 3 Binary Search Tree : Lowest Common Ancestor HackerRank Solution
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)
JavaScript Binary Search Tree : Lowest Common Ancestor HackerRank Solution
C Binary Search Tree : Lowest Common Ancestor HackerRank Solution
#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;
}
Leave a comment below
