Tuesday, December 1, 2015

Lowest Common Ancestor of a Tree

Hello guys, during one of my interview, the interviewer asked me something about the Lowest Common Ancestor. At first point it was a bit unusual thing as I never heard of it before, but when he explained me the stuff that what is a Lowest Common Ancestor, I found that it is quite good.

So here it goes lets suppose you have a tree like this:

The example is pretty clear. If you look closely you will find out that the lowest common ancestor is the common root for both the nodes. So:

  • If  you take the case of the 4, 5 the first common root (or more preferably ancestor/parent) is 2
  • If  you take the case of the 4, 6 the first common root (or more preferably ancestor/parent) is 1
Now the question arises how do we get to this using the program. So let me try to explain the simple solution what we can do for this to work:

First of all let us try to understand the basic traversing algos of the Trees (binary). These are as follows:
  1. In-Order(Left-Node-Right)
  2. Post-Order(Left-Right-Node)
  3. Pre-Order(Node-Left-Right)


So considering the above example, let us try to take out the In-Order and Pre-Order:
  • In-Order will be 4, 2, 12, 10, 13, 5, 11, 1, 6, 3, 8, 7, 9
  • Post-Order will be 4, 12, 13, 10, 11, 5, 2, 6, 8, 9, 7, 3, 1
Now after this we can say some of the key points, those are:
  1. The left subtree of any node is available in Inorder
  2. Now take all the subnodes of two nodes for which we have to find the LCA
  3. Now if you select the node at the maximum index in Post-order among all the nodes of step (2) list you will find the LCA.
Explanation:
The reason is very clear the Inorder gives you all the possible in between nodes of the 2 nodes for which you want to find the LCA. Now out of these nodes the root of these in between nodes, i.e LCA in other terms would be at last in Post order because by definition of Post order we always have the Node at the last. So considering this, if we want to get the LCA for Node 6 and Node 9 then the answer would be 3.

Note:
  • I have considered the above example for my reference and have created the code according to the above scenario, so please update it according to your needs.
  • The overall example and logic will remain the same only the creation of the tree will change. So the left and right might change in a tree.
  • I have just coded the basic one, didn't covered the edge cases and all the checks.
Working code here:

Java Code
package com.test.tree;

import java.util.ArrayList;
import java.util.List;

public class TreeTraversal {
 
 public static final List<Node> inOrderList = new ArrayList<>(); 
 public static final List<Node> preOrderList = new ArrayList<>();
 public static final List<Node> postOrderList = new ArrayList<>(); 

 public static void main(String[] args) {
  
  Node n1 = new Node(1);
  Node n2 = new Node(2);
  Node n3 = new Node(3);
  Node n4 = new Node(4);
  Node n5 = new Node(5);
  Node n6 = new Node(6);
  Node n7 = new Node(7);
  Node n8 = new Node(8);
  Node n9 = new Node(9);
  Node n10 = new Node(10);
  Node n11 = new Node(11);
  Node n12 = new Node(12);
  Node n13 = new Node(13);
  
  n1.left = n2;
  n1.right = n3;
  
  n2.left = n4;
  n2.right = n5;
  
  n3.left = n6;
  n3.right = n7;
  
  n4.left = n4.right = null;
  
  n5.left = n10;
  n5.right = n11;
  
  n6.left = n6.right = null;
  
  n7.left = n8;
  n7.right = n9;
  
  n10.left = n12;
  n10.right = n13;
 
  n11.left = n11.right = null;
  
  n8.left = n8.right = null;
  n9.left = n9.right = null;
  
  
  inOrder(n1);
  System.out.println("Inorder traversal is " + inOrderList);
  postOrder(n1);
  System.out.println("Postorder traversal is " + postOrderList);
  
  /*
   * 1. we take the list of nodes that are in between them
   * 2. then we take the address of each node of the above found list 
   * 3. the node that is in the farthest position, will be the LCA 
   */
  Node fn = n6;
  Node sn = n9;
  System.out.println("We are gonna find the LCA between " + fn + " & " + sn);
  List<Node> inBetweenList = inBetween(inOrderList, fn, sn);
  System.out.println("The nodes in between " + fn + " and " + sn + " are as follows " + inBetweenList);
  System.out.println("LCA of " + fn + " & " + sn + " is " + lca(inBetweenList, postOrderList));
 }
 
 public static List inBetween(List<node> inOrder, Node fn, Node sn){
  int i1 = inOrder.indexOf(fn);
  int i2 = inOrder.indexOf(sn);
  List<Node> result = i1 > i2 ? inOrder.subList(i2, i1 + 1) :  inOrder.subList(i1, i2 + 1);
  return result;
 }
 
 public static Node lca(List<node> inBetweenList, List<node> postOrderList){
  Node result = null;
  int maxIndex = 0;
  for(Node node : inBetweenList){
   maxIndex = postOrderList.indexOf(node) > maxIndex ? postOrderList.indexOf(node) : maxIndex;
  }
  
  result = postOrderList.get(maxIndex);
  return result;
 }
 
 public static void inOrder(Node root){
  if(root == null){
   return;
  }
  inOrder(root.left);
  inOrderList.add(root);
  inOrder(root.right);
 }
 
 public static void preOrder(Node root){
  if(root == null){
   return;
  }
  preOrderList.add(root);
  preOrder(root.left);
  preOrder(root.right);
  
 }
 
 public static void postOrder(Node root){
  if(root == null){
   return;
  }
  postOrder(root.left);
  postOrder(root.right);
  postOrderList.add(root);
 }
 
}


class Node{
 public Node left;
 public Node right;
 public int info;
 
 public Node(int info){
  this.info = info;
  this.left = null;
  this.left = null;
 }
 
 public String toString(){
  return "" + this.info;
 }
}

No comments:

Post a Comment