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:

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:

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:

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: