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

Deletion Operation of the binary search tree in C++ language

A typical binary search tree implements some order to carry out the arrangements. As the name suggests, each parent node should have at most two children. The main rule in...

4 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.

Pairwise swap elements of a given linked list

Pairwise swap elements of a given linked list In this problem, we have given a linked list, and we need to pairwise swap elements of the given linked list. Example:                                     Input:1 ->3...

4 minutes read.

Deletion in B+ Tree

Make a search for the leaf node that containing the key value by taking the value in a key value. If the required key value is found, then it will remove...

6 minutes read.

Sum of Nodes in a Binary Tree

In this article, we will see the sample problems that will help us understand the concept and summation of all the nodes in the binary tree. Implementation /* creating a program that...

4 minutes read.

Graph Data Structure

A graph is a non-primitive and non-linear data structure. It is a group of (V, E) where V is a set of vertexes, and E is a set of edge....

3 minutes read.

Rotate a Singly Linked List

Rotate a Singly Linked List This article will explain how we can rotate the singly linked list. Here we have given a singly linked list, and we need to rotate this...

4 minutes read.

AVL Tree

AVL Tree AVL Tree is referred to as self-balanced or height-balanced binary search tree where the difference between heights of its left subtree and right subtree (Balance Factor) can't more than...

25 minutes read.

How to get Better in Data Structures and Algorithms?

Introduction Data structures and algorithms are fundamental computer science concepts that store, organize, and process data efficiently. By understanding different data structures and algorithms and using them effectively, you can become...

19 minutes read.

Given a Binary Tree Check the Zig-Zag Traversal

Implementation // The C++ implementation of the zig-zag traversal method in the O(n) time.  #include <iostream> #include <stack> using namespace std; // creating a binary tree node. struct __nod { int record; struct __nod *Lft, *Rt; }; // creating a...

4 minutes read.

What is the difference between Tree and Graph

We usually use a diverse range of data structure to store our data and information. To store them in a more sequential manner and to access them easily, we use...

4 minutes read.

Convert Binary Tree into a Threaded Binary Tree

Implementation /*Writing a C++ program that will help us change the binary tree into a threaded binary tree and help us transform. */ #include <bits/stdc++.h> using namespace std; /*Creating the structure of a node...

11 minutes read.

AVL tree in data structure c++

AVL tree is generally known as the self-sustained and most balanced tree in the field of a binary search tree. It was also widely known as the height-balanced binary tree....

6 minutes read.

Find all possible words from board

We have been given a dictionary of words and a board of characters from which we can form strings. Now, we have to check if the string is present in...

5 minutes read.

Spanning Tree

Spanning Tree: The spanning tree is a subset of the graph. It is a non-cyclic graph. If any node in the spanning tree is truncated, the entire graph fails. There are...

10 minutes read.

Binary Search Tree vs AVL Tree: Data Structure

Difference Between Binary Search Tree and AVL Tree Binary Search Tree: The binary search tree is a kind of binary tree data structure and it follows the conditions of binary...

3 minutes read.

Blowfish algorithm

The Blowfish algorithm is the very first encryption algorithm which is symmetric. It was firstly used as an alternate algorithm for the DES algorithm. It was designed by Bruce Steiner...

3 minutes read.

Vertical Order Traversal of Binary Tree

Implementation #include <iostream> #include <vector> #include <map> using namespace std; // representing the primary model of a binary tree node. struct _nod { int ky; _nod *Lft, *Rt; }; // establishing a new function representing the new binary tree node. struct _nod*...

5 minutes read.

Remove duplicates from an unsorted Linked List

Remove duplicates from an unsorted Linked List This article will explain how we can remove duplicates from unsorted linked lists. Here we have given an unsorted singly linked list and will...

3 minutes read.

Bubble sort algorithm using Javascript

Sorting is a very useful technique in many algorithms and programs. Basically, sorting operations help us to arrange a set of data in a particular manner. Bubble sort is one...

3 minutes read.