Saturday, February 13, 2010

Least Common Ancestor without using a parent node in java

We already saw how to find the Least Common Ancestor for a binary tree. The problem gets a bit tricky when the node structure is like this.
class Node {
  Node left;
  Node right;
  int data;
 }
If you look at the above structure, there are no parent nodes and the given tree is not a Binary Search Tree which makes the problem all the more complicated.
To attack this problem we need to follow the below steps.
  1. Find the path of the first node using in-order traversal - Cost: O(n)
  2. Find the path of the second node using in-order traversal - Cost: O(n)
  3. Put the nodes of the first path in a set - Cost: O(logn)
  4. For each node in the second path check if it exists in the first path. The matching one would be the Least Common Ancestor - Cost: O(logn)
The total cost for this program would be - O(n) + O(n) + O(logn) + O(logn) = O(n).



Now for the java code. I am going to use the Trace Algorithm from the previous post for this solution to make life easier. Hope you were able to learn something.

package dsa.tree;

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

/**
 * Program to find the Least Common Ancestor without
 * for a Binary Tree (Not a BST). The Node does not have
 * a parent pointer. The direction of the tree is one sided
 * @author Braga
 *
 */
public class LCSBinaryTree {
 private Node n1,n2;
 
 public static void main(String args[]){
  LCSBinaryTree nodeFinder = new LCSBinaryTree();
  nodeFinder.find();
 }
 
 public void find(){
  Tree t = getSampleTree();
  Node commonParent = findCommonParent(t,n1,n2);
  if(commonParent == null){
   System.out.println("Common Parent for "+n1.data+" and "+n2.data+" is null");
  }else{
   System.out.println("Common Parent for "+n1.data+" and "+n2.data+" is "+commonParent.data);
  }
 }

 private Tree getSampleTree() {
  Tree bsTree = new BinarySearchTree();
  int randomData[] = {43,887,11,3,8,33,6,0,46,32,78,76,334,45};
  for(int i=0;i<randomData.length;i++){
   bsTree.add(randomData[i]);
  }
  n1 = bsTree.search(76);
  n2 = bsTree.search(334);
  return bsTree;
 }
 
 public Node findCommonParent(Tree t, Node node1, Node node2){
  TracePath pathTracer = new TracePath();
  
  /**
   * If either of the nodes is root, then there is no common
   * parent
   */
  if(node1.equals(t.getRoot()) || node2.equals(t.getRoot())){
   return null;
  }
  //Using the path tracer, find the path of two nodes in 2*O(n) time.
  Stack<Node> path1 = pathTracer.trace(t, node1);
  Stack<Node> path2 = pathTracer.trace(t, node2);
  
  //All that is left to do is to find the common parent now.
  Set<Node> firstPath = new HashSet<Node>();
  for(Node iNode:path1){
   firstPath.add(iNode);
  }
  while(!path2.isEmpty()){
   Node currentNode = path2.pop();
   if(firstPath.contains(currentNode)){
    if(!path2.isEmpty() && firstPath.contains(currentNode = path2.peek())){
     return path2.peek();
    }
    return currentNode;
   }
  }
  return null;
 }
}
//SAMPLE OUTPUTS
//Common Parent for 887 and 334 is 43
//Common Parent for 43 and 334 is null
//Common Parent for 6 and 334 is 43
//Common Parent for 76 and 334 is 46
Cheers,
Bragaadeesh.

17 comments:

santhosh said...

Hi Braga,

Nice job... But, I guess one particular use case may not be covered. Assume the findCommonParent is called for nodes 78 and 334. The answer should be 46. But, your code will return 78 (as 78 would be present in both the parts). Ma be you should just pop the last nodes in both the stacks before comparing them ? my solution will cover even that case where one of the inputs is root node. For eg. if 43 and 11 are the input nodes, the answer should be null and not 43. What is your opinion?

Bragadeesh said...

Thank you santhosh for pointing that out. Yes, you are correct. Say If someone asks common parent for me and my father, I would definitely not tell its my father. Its ofcourse my grandfather. Thank you very much for pointing that out.
I will update the program.

Bragaadeesh said...

**CODE UPDATED**
Code is now updated to handle common parent if one of the paths is the subpath of the other.
If either of the nodes have root, then there will not be any common parent.

Mavi Domates said...

That is correct my friend, thank you for replying (even though it is an awkward place =P), great job!

Bragaadeesh said...

@Mavi: You're most welcome!

Jay said...

Hi Bragadeesh,

Thanks for the solution. i would greatly appreciate if you help me understand your solution.
In the above example if we need to find the LCA of 45 and 78, Inorder traversals gives us
45:0,3,6,8,11,32,33,43
78:0,3,6,8,11,32,33,43,45,46,76

I didn't really understand the 4th point "The matching one would be the Least Common Ancestor"

So how do i proceed next?? (to 46 which is the answer)

Thanks in advance.

Bragaadeesh said...

@Jay:

Although we are doing in-order traversal internally, what we actually do is tracing the path. Please take a look here to understand the solution.

divya said...

hii..
really a very nice site!!
but, i am not getting one thing how will u search for every node in path 2 with every node in path 1 in logn. actually i dont know java so i hv not gone through code. can u please explain me the algo for that.
one more thing wat if two nodes have same data in the tree. does ur soln works for that.

thanks in advance..

Pawan said...

Hi Bragdeesh,

I think there can be a better solution with recursion... giving it here, as I am a C++ guy, so giving here in C++... please let me know if any bug....

struct Node
{
Node* left;
Node* right;
int info;
};

int FindLowestAncestor(Node* pCurNode, int searchNode1, int searchNode2, Node** ppAncestorNode)
{
int foundSelf = 0;
int foundLeft = 0;
int foundRight = 0;

if (pCurNode != NULL)
{
if ((pCurNode->info == searchNode1) || (pCurNode->info == searchNode2))
foundSelf = 1;

foundLeft = FindLowestAncestor(pCurNode->left, searchNode1, searchNode2, ppAncestorNode);
foundRight = FindLowestAncestor(pCurNode->right, searchNode1, searchNode2, ppAncestorNode);

if (((foundLeft + foundRight) == 2) && (*ppAncestorNode == NULL))
*ppAncestorNode = pCurNode;
}
return foundSelf + foundLeft + foundRight;
}

int main()
{
Node* pAncestorNode = NULL;
Node* root; //Set value to root of tree
int searchNode1 = 6;
int searchNode2 = 334;

int found = FindLowestAncestor(root, searchNode1, searchNode2, &pAncestorNode);

printf("Found %d Nodes ", found);

if (pAncestorNode)
printf("Value of Parent %d", pAncestorNode->info);

return 0;
}

--Pawan

Bragaadeesh said...

@Pawan : Nice!!

Maulish Soni said...

is tree is binary search tree then :

while( root != null ){
int value = root.getValue();
if( value > value1 && value > value2 ){
root = root.getLeft();
} else if( value < value1 && value < value2 ){
root = root.getRight();
} else {
return root;
}
}

return null; // only if empty tree


will work very well. Else other approach given which counts the number of nodes will be efficient.

b said...

@Moulish: Yes you are right. But in my experience, this common ancestor problem is usually associated with a Binary Tree rather a BST. Much appreciate your code snippet!!

Sushma said...

Hi,

Nice expalnation. one question is Common Parent for 76 and 334 is 46
isnt the common parent 78 here.

Sushma said...

Hi,

Nice expalnation. one question is Common Parent for 76 and 334 is 46
isnt the common parent 78 here.

b said...

@Shushma : You are correct. The common parent of 76 and 334 is 78. The example I've shown however is between 45 and 334.

Ragesh Sivakumar said...

Hello,

How to find distant between two nodes in b-tree??

Thanks

Ragesh Sivakumar said...

Also,

Anybody can tell me the answers of following questions??

#28 Question:
If X is the adjacency matrix of a graph G with no self loops, the entries along the principle diagonal of X are ______.
• a. all zeros
• b. all ones
• c. both zeros and ones
• d. different
#29 Question:
In which data structure do the insertion and deletion take place at the same end?
• a. Linked list
• b. Tree
• c. Stack
• d. Linked list of stack
#30 Question:
Suppose we have a circular array implementation of a queue, with ten items in the queue stored at data[2] through data[11]. The CAPACITY is 42. Where does the push member function place the new entry in the array?
• a. data[1]
• b. data[2]
• c. data[11]
• d. data[12]
#31 Question:
A simple graph in which there exists an edge between every pair of vertices is called a/an _________.
• a. incomplete graph
• b. complete graph
• c. Euler graph
• d. planner graph
#32 Question:
What will happen if in data structure a pop operation on the stack causes the stack pointer to move past the origin of the stack?
• a. Overflow
• b. Underflow
• c. Null
• d. Garbage collection
#33 Question:
Suppose T is a complete binary tree with 14 nodes. What would be the minimum possible depth of T?
• a. 0
• b. 3
• c. 4
• d. 5
#34 Question:
Which of the following statements about binary trees is false?
• a. Every Node must have at least two children
• b. Every non-empty tree has exactly one root node
• c. Every node has at the most two children
• d. None of the above
#35 Question:
Which operations require linear time for their worst-case behavior in the linked-list version of a queue?
• a. front
• b. push
• c. empty
• d. None of these operations require linear time
#36 Question:
The number of distinct simple graphs with up to three nodes is _______.
• a. 15
• b. 10
• c. 7
• d. 9
#37 Question:
Which of the following tree traversal techniques reads the root before its children nodes?
• a. In order
• b. Pre-order
• c. Post-order
• d. None of the above
#38 Question:
A matrix is called sparse when______
• a. most of its elements are non-zero
• b. most of its elements are zero
• c. all of its elements are non-zero
• d. None of the above
#39 Question:
In the linked representation of a sparse matrix, the head node for a column list stores_____
• a. a pointer to the next column head node
• b. a pointer to the first node in the column list
• c. column number
• d. All of the above
#40 Question:
The linked list implementation of sparse matrices is superior to the generalized dope vector method because it is __________.
• a. conceptually easier and completely dynamic
• b. efficient if the sparse matrix is a band matrix
• c. efficient in accessing an entry
• d. all of these