Find least or lowest common ancestor (LCA) in binary search tree (java/ example)

• Lowest or least common ancestor (LCA) of two nodes node1 and node2 in a binary tree is:
  • The lowest node in a binary tree that has both node1 and node2 as descendant nodes.
  • One node can be descendant of another node
    • If node2 is descendant node of node1, node1 will be LCA of node1 and node2.
• We are assuming both nodes exists in a binary search tree.
• We will use depth first traversal to find LCA in a binary search tree.
• We have already discussed finding lowest or least common ancestor in a binary tree

Examples to find LCA of input nodes:

LCA of input nodes using recursive algorithm is as follows:

Example 1: find LCA of Node J & Node K in a binary search tree (java)

• Find LCA (J,K) is Node G.
• The value at node G is lying within the value of node J and node K.
  • Node K > Node G > Node J (assuming unique values in BST).
  • There is no other node in a BST,  which is having value lying within node J and K.

Example 2: find LCA of node E & node G in BST using java

• Find LCA (E, G) is Node A.
• The value at node A is lying within the value of node E and node G (similar to example 1).

Example 3: find LCA of node G and node J in BST using java

• Find LCA (G, J) is Node G.
• Node J is descendant node of Node G and hence Node G is LCA.
• The ancestor (Node G) has value equals to one of node (node to be searched).

Conclusion: LCA node will have value within (or equal to any node) range of input nodes

Algorithm: find LCA(J,K) in binary search tree using java

• Node A, Node J and Node K input for our function
• Check value of node A is greater than J and K
  • 100 > 160 && 100 > 190?  No, its not true
• Check value of node A is less than J and K
  • 100 < 160 && 100 < 190 ? yes, its true
  • LCA of 160 and 190 is in right subtree.
  • Go to right child of A i.e. Node C
  • Node C, Node J and Node K input for recursive function
    • Check value of node C is greater than J and K
      • 150 > 160 && 150 > 190? , No, its not true
    • Check value of node C is less than J and K
      • 150 < 160 && 150 < 190?, yes its true
      • LCA of 160 and 190 is in right subtree.
      • Go to right child of C i.e. Node G
      • Node G, Node J and Node K input for recursive function
        • Check value of node G is greater than J and K
          • 175 > 160 && 175 > 190?, No its not true
        • Check value of node C is less than J and K
          • 175 < 160 && 175 < 190? , No its not true
        • Then its must be within 160 and 190 [implicit condition]
          • return LCA Node G from here
      • return Node G
  • return Node G
• return Node G

LCA (J, K ) = Node G,

Program: find least common ancestor in BST using recursive algorithm

1.) LCA Class:

• LCA class is used to find the least or lowest ancestor of two input nodes.
• Traverse the binary search tree using recursive algorithm.

package org.learn.Question;

import org.learn.PrepareTree.Node;

public class LCA {
	public static Node lca(Node root, Node A, Node B) {
		if (null == root) {
			return root;
		}

		if (root.data > A.data && root.data > B.data) {
			return lca(root.left, A, B);
		}

		if (root.data < A.data && root.data < B.data) {
			return lca(root.right, A, B);
		}

		return root;
	}
}

2.) Node Class :

• Node class representing the node of binary search tree.

package org.learn.PrepareTree;

public class Node {
	public int data;
	public Node left;
	public Node right;

	public Node(int num) {
		this.data = num;
		this.left = null;
		this.right = null;
	}

	public Node() {
		this.left = null;
		this.right = null;
	}
	public static Node createNode(int number) {
		return new Node(number);
	}
}

3.) App: 

• We are constructing the binary search tree in main method.
• We are calling the method LCA class, to find the lca of two input nodes.

package org.learn.Client;

import org.learn.PrepareTree.Node;
import org.learn.Question.LCA;

public class App 
{
    public static void main( String[] args )
    {  
       //root level 0
       Node A = Node.createNode(100);
       //Level 1
       Node B = Node.createNode(50);
       Node C = Node.createNode(150);
       //Level 2
       Node D = Node.createNode(25);
       Node E = Node.createNode(75);
       Node F = Node.createNode(125);
       Node G = Node.createNode(175);
       //Level 3
       Node H = Node.createNode(120);
       Node I = Node.createNode(140);
       Node J = Node.createNode(160);
       Node K = Node.createNode(190);
             
       //connect Level 0 and 1
       A.left = B;
       A.right = C;
       //connect level 1 and level 2
       B.left = D;
       B.right = E;
       C.left = F;
       C.right = G;
       //Connect level 2 and level 3
       F.left = H;
       F.right = I;
       G.left = J;
       G.right = K;
         
       Node ancestor = LCA.lca(A, J, K);
       System.out.printf("Ancestor of %d and %d is %dn",J.data,K.data,ancestor.data);
       
       ancestor = LCA.lca(A, J, G);
       System.out.printf("Ancestor of %d and %d is %dn",J.data,G.data,ancestor.data);
       
       ancestor = LCA.lca(A, E, G);
       System.out.printf("Ancestor of %d and %d is %dn",E.data,G.data,ancestor.data);
    }
}

Output : least common ancestors in binary search tree using java

Ancestor of 160 and 190 is 175
Ancestor of 160 and 175 is 175
Ancestor of 75 and 175 is 100

 Download Code – Least common ancestor (LCA) in BST