Last Updated on March 28, 2022 by Ria Pathak
Concepts Used
DFS , Recursion
Difficulty Level
Medium
Problem Statement :
"Lowest common ancestor of two node n1 and n2 is the lowest node in the tree that has both n1 and n2 as descendents(where we allow a node to be a descendant of itself)."Given a binary tree and two values, our task is to return the node which is lowest common ancestor of the two values.
See original problem statement here
Solution Approach :
Introduction :
Lowest Common Ancestor (LCA) of two nodes
n1andn2in the tree is the shared ancestor ofn1andn2that is located farthest from the root.
Method 1:
We can begin by storing path of each node starting from the root one-by-one.
By the definition of LCA above, we know that there must be some nodes (atleast one), which are common in both the paths we have stored. (Unless the root itself is LCA ).
Suppose we need to find LCA of the nodes
n1&n2. So,we will search for the nodesn1&n2in the given tree and store their paths starting from the root node. Now we will start traversing both the path arrays till the values stored in the arrays matches.As soon as the values become different we will stop & return the last value which matches both the path arrays. This value is our required LCA.
Method 2 (Efficient):
We can reduce the traversal to just once, without using any extra space using following points :
- If root matches any of the values
n1orn2, then root is the LCA.- Else, we will recurvisely call the function for its left & right subtrees. The node which has one value present in its left subtree and the other value present in right subtree is the LCA.
- If both values lies in the left subtree, then LCA lies in the left subtree, otherwise LCA lies in right subtree.
Complexity Analysis:
In the first method, although it is
O(n)in case of time complexity but we are traversing the arrays 3 times (twice for storing the path and once for finding the LCA), with an extra space for path arrays but in the second method we are traversing the array just once also the space complexity isO(1)of second method.
SOLUTIONS:
#include <stdio.h>
#include<stdlib.h>
#define ll long long
#define REP(i, n) for (i = 0; i < n; i++)
struct nodelist
{
ll value;
struct nodelist *left;
struct nodelist *right;
};
typedef struct nodelist node;
struct Queue
{
int front, rear, size;
unsigned capacity;
node* *array;
};
typedef struct Queue queue;
queue* createQueue(unsigned capacity)
{
queue* qu =(queue*)malloc(sizeof(queue));
qu->capacity = capacity;
qu->front = qu->size =0;
qu->rear = capacity-1;
qu->array = (node **)malloc(qu->capacity * sizeof(node));
return qu;
}
int isFull(queue* queue1)
{
return (queue1->size == queue1->capacity);
}
int isEmpty(queue* queue1)
{
return (queue1->size==0);
}
void enqueue(queue* queue1, node* item)
{
if(isFull(queue1))
return ;
queue1->rear = (queue1->rear +1 )%queue1->capacity;
queue1->array[queue1->rear] = item;
queue1->size = queue1->size +1;
}
node dequeue(queue* queue1)
{
node* item = queue1->array[queue1->front];
queue1->front = (queue1->front +1)%queue1->capacity;
queue1->size = queue1->size -1;
return *item;
}
node* front(queue* queue1)
{
return queue1->array[queue1->front];
}
node* rear(queue * queue1)
{
return queue1->array[queue1->rear];
}
node *createNode(ll value)
{
node *t= (node *) malloc(sizeof(node));
t->value = value;
t->right = t->left = NULL;
return t;
}
void deleteNode(node*t)
{
free(t);
}
node *replaceNegativeOne(node *root)
{
if(root==NULL ||(root->value == -1 && root->left == NULL && root->right == NULL))
return NULL;
root->left = replaceNegativeOne(root->left);
root->right = replaceNegativeOne(root->right);
return root;
}
void deleteTree(node *node1)
{
if(node1==NULL)
return;
deleteTree(node1->left);
deleteTree(node1->right);
free(node1);
}
node *createTreeByLevelTree()
{
ll n,m;
queue* queue1 = createQueue(100000);
node *root, *t;
root = NULL;
while(scanf("%lld", &n))
{
if(isEmpty(queue1))
{
root= createNode(n);
enqueue(queue1,root);
continue;
}
scanf("%lld", &m);
t = front(queue1);
dequeue(queue1);
t->left =createNode(n);
t->right=createNode(m);
if(t->left->value !=-1)
enqueue(queue1,t->left);
if(t->right->value !=-1)
enqueue(queue1,t->right);
if(isEmpty(queue1))
break;
}
return root;
}
node* findLowestAncestor(node* root, int v1, int v2)
{
if(root== NULL)
return root;
if(root->value == v1 || root->value == v2 )
return root;
node * left = findLowestAncestor(root->left,v1,v2);
node* right = findLowestAncestor(root->right,v1,v2);
if(left && right)
return root;
return (left)?left:right;
}
int main() {
node *root = NULL;
root = createTreeByLevelTree();
root = replaceNegativeOne(root);
int n1,n2;
scanf("%d %d",&n1,&n2);
node *val = findLowestAncestor(root, n1,n2);
printf("%lld\n", val->value);
deleteTree(root);
return 0;
}
#define REP(i, n) for (i = 0; i < n; i++)
#define pb(a) push_back(a)
#define vi vector<long>
#define ll long long
#include <bits/stdc++.h>
using namespace std;
struct node
{
ll value;
node *left;
node *right;
};
node *createNode(ll value)
{
node *t = new node();
t->value = value;
t->right = t->left = NULL;
return t;
}
void deleteNode(node *t)
{
delete t;
}
node *replaceNegativeOne(node *root)
{
if (root == NULL || (root->value == -1 && root->left == NULL && root->right == NULL))
return NULL;
root->left = replaceNegativeOne(root->left);
root->right = replaceNegativeOne(root->right);
return root;
}
node *createTreeByLevelTree()
{
ll n, m;
queue<node *> q;
node *root, *t;
root = NULL;
while (cin >> n)
{
if (q.empty())
{
root = createNode(n);
q.push(root);
continue;
}
cin >> m;
t = q.front();
q.pop();
t->left = createNode(n);
t->right = createNode(m);
if (t->left->value != -1)
{
q.push(t->left);
}
if (t->right->value != -1)
{
q.push(t->right);
}
if (q.empty())
{
break;
}
}
return root;
}
void deleteTree(node *node)
{
if (node == NULL)
return;
deleteTree(node->left);
deleteTree(node->right);
delete node;
}
node* findLowestAncestor(node* root,int v1, int v2)
{
if(root==NULL)
return root;
if(root->value == v1 || root->value == v2)
return root;
node* left = findLowestAncestor(root->left,v1,v2);
node* right = findLowestAncestor(root->right,v1,v2);
if(left && right)
return root;
return (left)?left:right;
}
int main()
{
node *root = NULL;
root = createTreeByLevelTree();
root = replaceNegativeOne(root);
int n1, n2;
cin>>n1>>n2;
node* val =findLowestAncestor(root,n1,n2);
cout<<val->value<<endl;
deleteTree(root);
return 0;
}
import java.util.LinkedList;
import java.util.*;
import java.util.Scanner;
import java.io.*;
class Node
{
long value;
Node left, right;
public Node(long item)
{
value = item;
left = right = null;
}
}
class BinaryTree {
Node root;
BinaryTree() {
root = null;
}
Node createNode(long value) {
Node t = new Node(value);
return t;
}
Node replaceNegativeOne(Node root) {
if (root == null || (root.value == -1 && root.left == null && root.right == null)) {
return null;
}
root.left = replaceNegativeOne(root.left);
root.right = replaceNegativeOne(root.right);
return root;
}
Node createTreeByLevelTree(Scanner sc ) {
long n, m;
LinkedList<Node> queue = new LinkedList<>();
Node t;
root = null;
while (sc.hasNext()) {
n = sc.nextLong();
if (queue.isEmpty()) {
root = createNode(n);
queue.add(root);
continue;
}
m = sc.nextLong();
t = queue.peekFirst();
queue.pop();
t.left = createNode(n);
t.right = createNode(m);
if (t.left.value != -1)
queue.add(t.left);
if (t.right.value != -1)
queue.add(t.right);
if (queue.isEmpty())
break;
}
return root;
}
void deleteTree(Node node) {
node = null;
}
Node findLowestAncestor(Node node, int v1, int v2) {
if(node == null)
return node;
if(node.value == v1 || node.value == v2)
return node;
Node left = findLowestAncestor(node.left,v1,v2);
Node right = findLowestAncestor(node.right,v1,v2);
if(left!=null && right!= null)
return node;
return (left!=null)?left:right;
}
}
public class Main {
public static void main(String[] args) {
// write your code here
Scanner sc = new Scanner(System.in);
BinaryTree bt = new BinaryTree();
bt.root = bt.createTreeByLevelTree(sc);
bt.root = bt.replaceNegativeOne(bt.root);
int n1 = sc.nextInt();
int n2 = sc.nextInt();
Node val = bt.findLowestAncestor(bt.root, n1,n2);
System.out.println(val.value);
bt.deleteTree(bt.root);
}
}
}
[forminator_quiz id="1705"]
This article tried to discuss the concept of DFS , Recursion. Hope this blog helps you understand and solve the problem. To practice more problems on DFS , Recursion you can check out MYCODE | Competitive Programming.