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