Lowest Common Ancestors of a Binary Tree in Java
The LCA is the lowest node in the tree from which both n1 and n2 descend, with n1 and n2 serving as the nodes for which the LCA is sought. The shared ancestor of nodes n1 and n2 that is the furthest away from the root is thus the LCA of a binary tree that includes nodes n1 and n2.
The lowest common ancestor in a binary tree You can do the following by preserving the routes from the root to nodes n1 and n2.
Application of the Least Common Ancestor (LCA):
In a tree, the distance from n1 to n2 is calculated as the sum of the distances from the root to n1 and the root to n2, divided by twice the distance from the root to their most recent common ancestor.
To solve the problem, follow these steps given below:
- Locate a route that leads from the root to n1 and save it as a vector or array.
- Discover a route from the root to n2, then record it in a different vector or array.
- Continue down both routes until the array values are identical. Just before the mismatch, return the common element.
BinaryTree.java
// The below code is about the lowest common ancestor for the binary tree
// The time complexity of the below code is O ( n )
// the two values are given, i.e., n1 and n2
// importing required packages
import java. util.ArrayList ;
import java. util.List;
// It is about a node of a binary tree
class Node {
int value ;
Node lef, rig ;
Node ( int dat )
{
value = dat ;
lef = rig = null ;
}
}
public class BinaryTree {
Node ro ;
private List < Integer > lst1 = new ArrayList < > ( ) ;
private List < Integer > lst2 = new ArrayList < > ( ) ;
// Finds the route through the tree's root node to the specified root.
int findingLowestCA ( int n1, int n2 )
{
lst1. clear ( ) ;
lst2. clear ( ) ;
return findingLowestCAInt ( ro, n1, n2 ) ;
}
private int findingLowestCAInt ( Node ro, int n1, int n2 )
{
if (! findingPath ( ro, n1, lst1 )|| ! findingPath ( ro, n2, lst2 ) )
{
System.out.println ( ( lst1 . size ( ) > 0 )? " n1 is present ": " n1 is missing " ) ;
System.out.println ( ( lst2 . size ( ) > 0 )? " n2 is present " : " n2 is missing " ) ;
return -1 ;
}
int i ;
for ( i = 0 ; i < lst1 . size ( ) && i < lst2 . size ( ) ;i++ ) {
if ( ! lst1 . get ( i ) . equals ( lst2 . get ( i ) ) )
break ;
}
return lst1 . get ( i - 1) ;
}
// Determines the path from the root node to the provided root of the tree, Returns the path stored in a vector path. true if the path exists, false otherwise
private boolean findingPath ( Node ro, int n,List < Integer > lst )
{
// The below condition is the base case
if ( ro == null ) {
return false ;
}
lst.add(ro.value ) ;
if ( ro . value == n) {
return true ;
}
if ( ro . lef != null
&& findingPath ( ro . lef, n, lst ) ) {
return true ;
}
if ( ro . rig != null
&& findingPath ( ro . rig, n, lst ) ) {
return true ;
}
// If the condition is true, delete the root from the path [ ] and return false.
lst. remove ( lst. size ( ) - 1 ) ;
return false ;
}
// The below code is the Driver code
public static void main ( String [ ] args )
{
BinaryTree tr= new BinaryTree ( ) ;
tr.ro = new Node ( 1 ) ;
tr.ro.lef = new Node ( 2 ) ;
tr.ro.rig = new Node ( 3 ) ;
tr.ro.lef.lef = new Node ( 4 ) ;
tr.ro.lef.rig = new Node ( 5 ) ;
tr.ro.rig.lef = new Node ( 6 ) ;
tr.ro.rig.rig = new Node ( 7 ) ;
System.out.println ( " Lowest Common Ancestor ( 4, 5 ) = "+ tr . findingLowestCA ( 4, 5 ) ) ;
System.out.println ( " Lowest Common Ancestor ( 4 , 6 ) = "+ tr . findingLowestCA ( 4, 6 ) ) ;
System.out .println ( " Lowest Common Ancestor ( 3 , 4 ) = "+ tr . findingLowestCA ( 3, 4 ) ) ;
System.out.println ( " Lowest Common Ancestor ( 2, 4 ) = "+ tr . findingLowestCA ( 2, 4 ) ) ;
}
}
Output:
Lowest Common Ancestor ( 4 , 5 ) = 2
Lowest Common Ancestor ( 4 , 6 ) = 1
Lowest Common Ancestor ( 3 , 4 ) = 1
Lowest Common Ancestor ( 2, 4 ) = 2
A binary tree's lowest common ancestor when traversed only once:
- The goal is to climb the tree from the root up. If any of the provided keys match the root, then LCA is the root.
- The LCA is the node where one key is located in the left subtree, and the other in the right subtree.
- The left subtree likewise has LCA if both keys are located there.
- Otherwise, the appropriate subtree is LCA.
BinaryTree.java
// importing required packages
import java. util.ArrayList ;
import java. util.List;
class Node {
int value ;
Node lef, rig ;
Node ( int dat )
{
value = dat ;
lef = rig = null ;
}
}
public class BinaryTree {
// Root node for the Binary Tree
Node root;
Node findLCA(int n1, int n2)
{
return findLCA(root, n1, n2);
}
Node findLCA(Node node, int n1, int n2)
{
// Base condition
if (node == null)
return null;
if (node.value == n1 || node.value == n2)
return node;
Node left_lca = findLCA(node.lef, n1, n2);
Node right_lca = findLCA(node.rig, n1, n2);
if (left_lca != null && right_lca != null)
return node;
return (left_lca != null) ? left_lca : right_lca;
}
// Main section of the program from where execution begins
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.lef = new Node(2);
tree.root.rig = new Node(3);
tree.root.lef.rig = new Node(4);
tree.root.lef.lef = new Node(5);
tree.root.rig.lef = new Node(6);
tree.root.rig.rig = new Node(7);
System.out.println("LCA(4, 5) = "+ tree.findLCA(4, 5).value);
System.out.println("LCA(4, 6) = "+ tree.findLCA(4, 6).value);
System.out.println("LCA(3, 4) = "+ tree.findLCA(3, 4).value);
System.out.println("LCA(2, 4) = "+ tree.findLCA(2, 4).value);
}
}
Output
LCA(4, 5) = 2
LCA(4, 6) = 1
LCA(3, 4) = 1
LCA(2, 4) = 2
Time Complexity: O(N) because the technique does a simple tree traversal from the bottom up.
Auxiliary Space:
O(H), where H is tree's height.
It should be emphasised that the preceding method implies the Binary Tree contains keys. If one key exists but the other does not, LCA returns the current key. This approach can be extended to cover all occurrences by first establishing whether n1 and n2 are present in the tree and then computing the LCA of n1 and n2. Traverse the binary tree for each n1 and n2 nodes individually to see if the node is present.
BinaryTree.java
// importing required packages
import java. util.ArrayList ;
import java. util.List;
class Node {
int value ;
Node lef, rig ;
Node ( int dat )
{
value = dat ;
lef = rig = null ;
}
}
public class BinaryTree {
Node ro ;
private List < Integer > lst1 = new ArrayList < > ( ) ;
private List < Integer > lst2 = new ArrayList < > ( ) ;
int findingLowestCA ( int n1, int n2 )
{
lst1. clear ( ) ;
lst2. clear ( ) ;
return findingLowestCAInt ( ro, n1, n2 ) ;
}
private int findingLowestCAInt ( Node ro, int n1, int n2 )
{
if (! findingPath ( ro, n1, lst1 )|| ! findingPath ( ro, n2, lst2 ) )
{
System.out.println ( ( lst1 . size ( ) > 0 )? " n1 is present ": " n1 is missing " ) ;
System.out.println ( ( lst2 . size ( ) > 0 )? " n2 is present " : " n2 is missing " ) ;
return -1 ;
}
int i ;
for ( i = 0 ; i < lst1 . size ( ) && i < lst2 . size ( ) ;i++ ) {
if ( ! lst1 . get ( i ) . equals ( lst2 . get ( i ) ) )
break ;
}
return lst1 . get ( i - 1) ;
}
private boolean findingPath ( Node ro, int n,List < Integer > lst )
{
// The below condition is the base case
if ( ro == null ) {
return false ;
}
lst.add(ro.value ) ;
if ( ro . value == n) {
return true ;
}
if ( ro . lef != null
&& findingPath ( ro . lef, n, lst ) ) {
return true ;
}
if ( ro . rig != null
&& findingPath ( ro . rig, n, lst ) ) {
return true ;
}
lst. remove ( lst. size ( ) - 1 ) ;
return false ;
}
public static void main ( String [ ] args )
{
BinaryTree tr= new BinaryTree ( ) ;
tr.ro = new Node ( 1 ) ;
tr.ro.lef = new Node ( 2 ) ;
tr.ro.rig = new Node ( 3 ) ;
tr.ro.lef.lef = new Node ( 4 ) ;
tr.ro.lef.rig = new Node ( 5 ) ;
tr.ro.rig.lef = new Node ( 6 ) ;
tr.ro.rig.rig = new Node ( 7 ) ;
System.out.println ( " Lowest Common Ancestor ( 4, 5 ) = "+ tr . findingLowestCA ( 4, 5 ) ) ;
System.out.println ( " Lowest Common Ancestor ( 4 , 6 ) = "+ tr . findingLowestCA ( 4, 6 ) ) ;
System.out .println ( " Lowest Common Ancestor ( 3 , 4 ) = "+ tr . findingLowestCA ( 3, 4 ) ) ;
System.out.println ( " Lowest Common Ancestor ( 2, 4 ) = "+ tr . findingLowestCA ( 2, 4 ) ) ;
}
}
Output:
Lowest Common Ancestor ( 4 , 5 ) = 2
Lowest Common Ancestor ( 4 , 6 ) = 1
Lowest Common Ancestor ( 3 , 4 ) = 1
Lowest Common Ancestor ( 2, 4 ) = 2