LCA (Lowest common ancestor) – binary tree (recursive / example)

• Given a binary tree, find least or lowest common ancestor (LCA) of two given nodes.
• Given input nodes should exists in a binary tree.
• We will use depth first search (DFS) recursive algorithm to traverse the binary tree.
• We have discussed the similar problem Find LCA in BST

Example of least common ancestor nodes is:

We will analyse the Fig 1 binary tree and find out the LCA of nodes lying in different subtrees.

Example 1: LCA of Node B (25) & C (75) of a binary tree. (Fig 2).

• Perform depth first search traversal.
• Traverse left subtree of Node A & We will find node B (input node).
  • Node B will send its reference to its parent (Node A).
• Traverse right  subtree of Node A & We will find node C (input node).
  • Node C will send its reference to its parent (Node A)
• Node A getting non null from its left and right subtree.
  • Node A will be LCA of Node B & Node C

Example 2: LCA of Node B (25) and D (10) of a binary tree. (Fig 3).

• Perform DFS traversal of binary tree.
• Traverse the left subtree of Node A.
  • We found Node B (whose LCA we would like to find).
  • No need to traverse underlying nodes).
  • return node B to its parent node A.
• Traverse the right subtree of Node A.
  • In right subtree traversal (Node C), we will not get node B or D.
  • Right subtree will return null to its parent node A.
• Node A will get node B from left subtree & null from right subtree.
• Non null value i.e. Node B will be LCA of Node B & Node D.

Example 3: LCA of Node I & Node K (refer Fig 4).

• Perform DFS traversal of binary tree to find LCA of Node I & K
• Traverse left subtree of node A ie Node B
  • Traverse left subtree of Node B i.e. Node D
    • Right subtree traversal of Node D will find Node I.
    • Node D will return reference of Node I to Node B.
  • Traverse right subtree of Node B i.e. Node E
    • Right subtree traversal of Node E will find Node K.
    • Node D will return reference of Node K to Node B.
  • Node B got node I from left subtree and Node K from right subtree
    • return Node B to its parent i.e. Node A.
• Traverse right subtree of Node A i.e. Node C.
  • Traverse left & right subtrees of Node C
  • No match will be found & return null to Node A.
• Node A will get Node B from left subtree & null from right subtree.
• Node B will LCA of Node I & Node K.

Example 4: LCA of Node I and Node M (refer Fig 5).

We can analyse the Fig 5 similar to previous examples.
Time complexity of algorithm is O(n).

Program to find lowest common ancestor of input nodes.

1.) LCA Class: LCA class is responsible for finding lowest common ancestors of two input nodes in a given binary tree.

 
package org.learn.Question;

public class LCA {
	public static Node lca(Node root, Node node1, Node node2) {
		if (null == root) {
			return root;
		}
		if (root == node1 || root == node2) {
			return root;
		}
		Node left = lca(root.left, node1, node2);
		Node right = lca(root.right, node1, node2);

		if (left != null && right != null) {
			return root;
		}
		if (left != null)
			return left;
		else
			return right;
	}
}

2.) Node Class: Node class is representing the nodes of a given binary tree.

package org.learn.Question;

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 Class: We are creating the binary tree in a main method & calling method of LCA class to find least or lowest common ancestor of two input nodes of a given binary tree.

package org.learn.Client;

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

public class App {
	public static void main(String[] args) {
		// root level 0
		Node A = Node.createNode(50);
		// Level 1
		Node B = Node.createNode(25);
		Node C = Node.createNode(75);
		// Level 2
		Node D = Node.createNode(15);
		Node E = Node.createNode(40);
		Node F = Node.createNode(60);
		Node G = Node.createNode(95);

		// Level 3
		Node H = Node.createNode(10);
		Node I = Node.createNode(20);
		Node J = Node.createNode(30);
		Node K = Node.createNode(45);
		Node L = Node.createNode(55);
		Node M = Node.createNode(65);

		// 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
		D.left = H;
		D.right = I;
		E.left = J;
		E.right = K;
		F.left = L;
		F.right = M;

		Node lca = LCA.lca(A, D, H);
		String message = String.format("1. LCA[Node D (%d) & Node H (%d)] = %d",
													D.data,H.data,lca.data);
		System.out.println(message);

		lca = LCA.lca(A, I, K);
		message = String.format("2. LCA[Node I (%d) & Node K (%d)] = %d", 
													I.data, K.data, lca.data);
		System.out.println(message);

		lca = LCA.lca(A, I, M);
		message = String.format("3. LCA[Node I (%d) & Node M (%d)] = %d", 
													I.data, M.data, lca.data);
		System.out.println(message);
	}
}

Output: Least common ancestors of input nodes :

1. LCA[Node D (15) & Node H (10)] = 15
2. LCA[Node I (20) & Node K (45)] = 25
3. LCA[Node I (20) & Node M (65)] = 50

Download Code – Find LCA of two node in a binary tree