Logo
×

LCA of binary tree

Implementation

//Writing a program to find the lowest common factor in a given binary search tree.
#include <iostream>
#include <vector>


using namespace std;


// the very first step is to create a binary tree.
struct __nod
{
	int ky;
	struct __nod *Lft, *Rt;
};


// Next, we will have to create a utility function that will create a binary tree with a new node with a key. 
__nod * new__nod(int s)
{
	__nod *temp = new __nod;
	temp->ky = s;
	temp->Lft = temp->Rt = NULL;
	return temp;
}


// now, as a next step, we have to look for the path or trail starting from the root node to the root of the tree, which will secure the path of the tree only if the path already exists; otherwise, it will transmit a false value.  
bool find__Path(__nod *root, vector<int> &path, int s)
{
	if (root == NULL) return false;


	// we have to store or push the given node into the vector. 
// it is known that if the node is not in the path, it will be removed from k. 
	path.push_back(root->ky);


	// check whether the value of k is the same as the node's key values.
	if (root->ky == k)
		return true;


	// check whether k is present in the left or right subtree.
	if ( (root->Lft && find__Path(root->Lft, path, k)) ||
		(root->Rt && find__Path(root->Rt, path, k)) )
		return true;


	// By any chance, if the subtree is not present in the root, remove it from the path, and then we have to establish the false value.
	path.pop_back();
	return false;
}
// We have to return the value of the LCA if the nodes g1 and g2 are already present in the given binary tree. 
//if this doesn't happen, we can return the -1 value.
int findLCA(__nod *root, int g1, int g2)
{
	// we have to establish and keep the values in g1 and g2.
	vector<int> path1, path2;


	// next, we have to look for the paths from the root to g1 and g2; if we don't find them, then we have to return the -1 value.  
	if ( !find__Path(root, path1, g1) || !find__Path(root, path2, g2))
		return -1;


	//we have to compare the paths to get the different sets of values.
	int i;
	for (i = 0; i < path1.size() && i < path2.size() ; i++)
		if (path1[i] != path2[i])
			break;
	return path1[i-1];
}


// writing the main code.
int main()
{
	// Let us create the Binary Tree shown in the above diagram.
	__nod * root = new__nod(1);
	root->Lft = new__nod(2);
	root->Rt = new__nod(3);
	root->Lft->Lft = new__nod(4);
	root->Lft->Rt = new__nod(5);
	root->Rt->Lft = new__nod(6);
	root->Rt->Rt = new__nod(7);
	cout << "LCA(4, 5) = " << findLCA(root, 4, 5);
	cout << "\nLCA(4, 6) = " << findLCA(root, 4, 6);
	cout << "\nLCA(3, 4) = " << findLCA(root, 3, 4);
	cout << "\nLCA(2, 4) = " << findLCA(root, 2, 4);
	return 0;
}

Output:

LCA of binary tree

Example 2)

//Writing a program to find the lowest common factor in a given binary search tree.
using System.Collections;
using System;
// the very first step is to create a binary tree.
class __nod
{
public int record;
public __nod Lft, Rt;


public __nod(int value)
{
	record = value;
	Lft = Rt = null;
}
}


public class BT_NoParentPtr_Solutiog1
{


__nod root;
private ArrayList path1 =
		new ArrayList();
private ArrayList path2 =
		new ArrayList();
// Next, we will have to create a utility function that will create a binary tree with a new node with a key. 


int findLCA(int g1,
			int g2)
{
	path1.Clear();
	path2.Clear();
	return findLCAInternal(root,
						g1, g2);
}


private int findLCAInternal(__nod root,
							int g1, int g2)
{
if (!find__Path(root, g1, path1) ||
	!find__Path(root, g2, path2)) {
	Console.Write((path1.Count > 0) ?
				"g1 is present" :
				"g1 is missing");
	Console.Write((path2.Count > 0) ?
				"g2 is present" :
				"g2 is missing");
	return -1;
}


int i;
for (i = 0; i < path1.Count &&
	i < path2.Count; i++)
{
	// System.out.println(path1.get(i)
	// + " " + path2.get(i));
	if ((int)path1[i] !=
		(int)path2[i])
	break;
}
return (int)path1[i - 1];
}
// now, as a next step, we have to look for the path or trail starting from the root node to the root of the tree, which will secure the path of the tree only if the path already exists; otherwise, it will transmit a false value.  
private bool find__Path(__nod root,
					int n,
					ArrayList path)
{
if (root == null)
{
	return false;
}
// we have to store or push the given node into the vector. 
// it is known that if the node is not in the path, it will be removed from k. 
path.Add(root.record);


if (root.record == n)
{
	return true;
}


if (root.Lft != null &&
	find__Path(root.Lft,
			n, path))
{
	return true;
}


if (root.Rt != null &&
	find__Path(root.Rt,
			n, path))
{
	return true;
}
// By any chance, if the subtree is not present in the root, remove it from the path, and then we have to establish the false value.
path.RemoveAt(path.Count - 1);


return false;
}
// writing the main code.
public static void Main(String[] args)
{
BT_NoParentPtr_Solutiog1 tree =
	new BT_NoParentPtr_Solutiog1();


tree.root = new __nod(1);
tree.root.Lft = new __nod(2);
tree.root.Rt = new __nod(3);
tree.root.Lft.Lft = new __nod(4);
tree.root.Lft.Rt = new __nod(5);
tree.root.Rt.Lft = new __nod(6);
tree.root.Rt.Rt = new __nod(7);


Console.Write("LCA(4, 5): " +
				tree.findLCA(4, 5));
Console.Write("\nLCA(4, 6): " +
				tree.findLCA(4, 6));
Console.Write("\nLCA(3, 4): " +
				tree.findLCA(3, 4));
Console.Write("\nLCA(2, 4): " +
				tree.findLCA(2, 4));
}
}

Output:

LCA of binary tree

Example 3)

//Writing a program to find the lowest common factor in a given binary search tree.
import java.util.ArrayList;
import java.util.List;
// the very first step is to create a binary tree.
class __nod {
	int record;
	__nod Lft, Rt;


	__nod(int value) {
		record = value;
		Lft = Rt = null;
	}
}


public class BT_NoParentPtr_Solutiog1
{


	__nod root;
	private List<Integer> path1 = new ArrayList<>();
	private List<Integer> path2 = new ArrayList<>();
// Next, we will have to create a utility function that will create a binary tree with a new node with a key. 
	int findLCA(int g1, int g2) {
		path1.clear();
		path2.clear();
		return findLCAInternal(root, g1, g2);
	}


	private int findLCAInternal(__nod root, int g1, int g2) {


		if (!find__Path(root, g1, path1) || !find__Path(root, g2, path2)) {
			System.out.println((path1.size() > 0) ? "g1 is present" : "g1 is missing");
			System.out.println((path2.size() > 0) ? "g2 is present" : "g2 is missing");
			return -1;
		}


		int i;
		for (i = 0; i < path1.size() && i < path2.size(); i++) {
			
		// System.out.println(path1.get(i) + " " + path2.get(i));
			if (!path1.get(i).equals(path2.get(i)))
				break;
		}


		return path1.get(i-1);
	}
// now, as a next step, we have to look for the path or trail starting from the root node to the root of the tree, which will secure the path of the tree only if the path already exists; otherwise, it will transmit a false value.  
	private boolean find__Path(__nod root, int n, List<Integer> path)
	{
		// base case
		if (root == null) {
			return false;
		}
// we have to store or push the given node into the vector. 
// it is known that if the node is not in the path, it will be removed from k. 
	// check whether the value of k is the same as the node's key values.
		path.add(root.record);


		if (root.record == n) {
			return true;
		}


		if (root.Lft != null && find__Path(root.Lft, n, path)) {
			return true;
		}


		if (root.Rt != null && find__Path(root.Rt, n, path)) {
			return true;
		}
// check whether k is present in the left or right subtree.
// By any chance, if the subtree is not present in the root, remove it from the path, and then we have to establish the false value.


		path.remove(path.size()-1);


		return false;
	}
// writing the main code.


	public static void main(String[] args)
	{
		BT_NoParentPtr_Solutiog1 tree = new BT_NoParentPtr_Solutiog1();
		tree.root = new __nod(1);
		tree.root.Lft = new __nod(2);
		tree.root.Rt = new __nod(3);
		tree.root.Lft.Lft = new __nod(4);
		tree.root.Lft.Rt = new __nod(5);
		tree.root.Rt.Lft = new __nod(6);
		tree.root.Rt.Rt = new __nod(7);


		System.out.println("LCA(4, 5): " + tree.findLCA(4,5));
		System.out.println("LCA(4, 6): " + tree.findLCA(4,6));
		System.out.println("LCA(3, 4): " + tree.findLCA(3,4));
		System.out.println("LCA(2, 4): " + tree.findLCA(2,4));
	
	}
}

Output:

LCA of binary tree

Example 4)

//Writing a program to find the lowest common factor in a given binary search tree.
// the very first step is to create a binary tree.
class __nod:
	# Constructor to create a new binary __nod
	def __init__(self, ky):
		self.ky = ky
		self.Lft = None
		self.Rt = None
// Next, we will have to create a utility function that will create a binary tree with a new node with a key. 
// now, as a next step, we have to look for the path or trail starting from the root node to the root of the tree, which will secure the path of the tree only if the path already exists; otherwise, it will transmit a false value.  
def find__Path( root, path, k):
	if the root is None:
		return False
// we have to store or push the given node into the vector. 
// it is known that if the node is not in the path, it will be removed from k. 
	// check whether the value of k is the same as the node's key values.
	path.append(root.ky)


	// check whether the value of k is the same as the node's key values.
	if root.ky == k :
		return True


	# Check if k is found in the Left or Right sub-tree
	if ((root.Lft != None and find__Path(root.Lft, path, k)) or
			(root.Rt!= None and find__Path(root.Rt, path, k))):
		return True
// check whether k is present in the left or right subtree.
// By any chance, if the subtree is not present in the root, remove it from the path, and then we have to establish the false value.
	path.pop()
	return False
// We have to return the value of the LCA if the nodes g1 and g2 are already present in the given binary tree. 
//if this doesn't happen, we can return the -1 value.
def findLCA(root, g1, g2):


	# To push the g1 and g2 values from the root node.
	path1 = []
	path2 = []
// we have to establish and keep the values in g1 and g2.
	// next, we have to look for the paths from the root to g1 and g2; if we don't find them, then we have to return the -1 value.  
	if (not find__Path(root, path1, g1) or not find__Path(root, path2, g2)):
		return -1
	i = 0
	while(i < len(path1) and i < len(path2)):
		if path1[i] != path2[i]:
			break
		i += 1
	return path1[i-1]
//we have to compare the paths to get the different sets of values.
// writing the main code.
root = __nod(1)
root.Lft = __nod(2)
root.Rt = __nod(3)
root.Lft.Lft = __nod(4)
root.Lft.Rt = __nod(5)
root.Rt.Lft = __nod(6)
root.Rt.Rt = __nod(7)


print ("LCA(4, 5) = %d" %(findLCA(root, 4, 5,)))
print ("LCA(4, 6) = %d" %(findLCA(root, 4, 6)))
print ("LCA(3, 4) = %d" %(findLCA(root,3,4)))
print ("LCA(2, 4) = %d" %(findLCA(root,2, 4)))

Output:

LCA of binary tree

Related Topics

What is a Tree in Terms of a Graph?

To know the explanation of trees in terms of graphs, we need first to know what trees and graphs are. So let us first learn about trees and graphs. Trees and...

6 minutes read.

Bitonical Sort

Arranging an unordered collecttion of things into asignificant order. •Comparision Based Model: Bubble Sort, Selection Sort -->Non-Comparison Based. Model: Bucket Sort or on the other hand a Count Sort Bitonic Sort: Bitonic sort Algorithm was made...

5 minutes read.

Post-order traversal in a binary tree

We all know that postorder is a form of tree traversal to visit the tree's nodes, and it helps us reach out to the tree's nodes. Postorder means visiting the...

4 minutes read.

Function to Insert a Node in a Binary Search Tree

Implementation // writing C++ code that will help us in implementing the insertion operation in a binary search tree. #include <bits/stdc++.h> using namespace std; // creating a new binary search tree node struct __nod { int...

8 minutes read.

Polish Notation in Data Structures

Arithmetic Expression: An arithmetic expression is defined as several operands or data items combined using several operators. For example; a+b*(c-d) is an expression. Operands: Operands represent the data in an expression...

2 minutes read.

Rearrange a linked list into alternate fashion first and the last element

Rearrange a linked list into alternate fashion first and the last element This article will explain how to rearrange the linked list into alternate fashion first and the last element. Here,...

3 minutes read.

What is a Spanning Tree in Data Structure

Data structures Data management is called database management. This allows the computer to sort or organize the data for efficient retrieval. A data model is a system used to store, manage,...

5 minutes read.

Stack Data Structure

The stack is a non-primitive and linear data structure. It works on the principle of LIFO (Last In First Out). That is, the element that is added to the end...

3 minutes read.

Given a Binary Tree, Print the Pre-order Traversal in Recursive

Implementation #include <stdio.h> #include <stdlib.h>   /* Creating a binary tree node that consists of some data along with the pointer to the left and right child.  */ struct __nod {     int record;     struct...

4 minutes read.

Fundamental of Algorithms

An algorithm is a part of any programming solution or coding. If we have to make a solution then first we have to think of a clear idea about the...

13 minutes read.

B Tree vs B + Tree: Data Structure

Difference Between B Tree and B+ Tree What is B Tree? B-Tree is a self-balancing or special type of m-way tree. B-Trees are used mainly in disc access. If we want...

3 minutes read.

Heap Sort vs Merge Sort

In this article, we are going to discuss the Heap Sort, Merge sort and the difference between them. What is Heap Sort? Heap – A heap is an abstract data type categorised...

7 minutes read.

What is a 2-3 Tree in Data Structure?

Tree Data structure The information about the tree is self-explanatory. Trees are ordered and, therefore, not linear. But they are actually designed differently. Tree A node-based data model that represents and...

5 minutes read.

Reverse the Singly Linked List in C

Reverse the Singly Linked List in C This article has given a singly linked list and will reverse the linked list by changing the links between nodes. Example:                         Input:  2 -> 4...

3 minutes read.

Extended Binary Tree

An extended binary tree is a binary tree in which all the NILL subtrees present mainly in the original trees are exchanged with the special nodes that are primarily known...

3 minutes read.

Linear Search

Searching: In the data structure, searching is the process in which an element is searched in a list that satisfies one or more than one condition. Types of searching There are two...

4 minutes read.

Red-black Tree in Data Structures?

A type of binary tree which is known as the Red-Black tree, is a specialized and unique tree. What is the urgency or, to be more precise, the necessity of...

10 minutes read.

Stack vs Array

Difference between Array and Stack In this article, we are going to discuss the major differences between the stack and array data structures: Array – In the data structure, the array is...

3 minutes read.

Count pairs from two linked lists whose sum is equal to a given value

Count pairs from two linked lists whose sum is equal to a given value In this problem, we have given two linked lists of size n1 and n2 with distinct elements...

4 minutes read.

Sorting Algorithms

Sorting: In the data structure, sorting is the process by which you arrange the data in a logical order. This logical order can also be an ascending order or a...

7 minutes read.