10 February 2010

Find common parent in a binary search tree in Java

This is a very famous question that many already are aware of. But I wanted to give a comprehensive working program in java to implement this with illustration. Consider the following binary tree which infact is a binary search tree.



The idea is very simple. For the first node traverse up till you reach root, while doing so, put the nodes in a hash set. Then do the same for the second node ie, try to traverse towards the root. Amidst doing that search for the existence of this node in the hash set we already created for the first traversal.
The place where those two nodes matches will be the common node. For any two nodes in a tree, there will be at least one common node which will be the root. I have given two examples below. One having a node other than root as the common parent and the other with root as the common parent.
The green line shows the traversal of first node path. Red shows the second node's path. The intersection or the common parent is shown in a blue circle.





Now for the Java source.
package dsa.tree;

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

public class FindCommonNode {
 private Node n1,n2;
 
 public static void main(String args[]){
  FindCommonNode nodeFinder = new FindCommonNode();
  nodeFinder.find();
 }
 
 public void find(){
  Tree t = getSampleTree();
  Node commonParent = findCommonParent(t,n1,n2);
  System.out.println("Common Parent : "+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(45);
  n2 = bsTree.search(334);
  return bsTree;
 }
 
 public Node findCommonParent(Tree t, Node node1, Node node2){
  Set<Node> firstNodeAddrSet = new HashSet<Node>();
  //Traverse till root
  while(node1!=null){
   firstNodeAddrSet.add(node1);
   node1 = node1.parent;
  }
  while(!firstNodeAddrSet.contains(node2) && node2!=null){
   node2 = node2.parent;
  }
  return node2;
 }
}

The implementations for Tree and BinarySearchTree can be found here.

Cheers,
Bragaadeesh.

4 comments:

Mavi Domates said...

this solution actually has problems. If the nodes have only the left and right pointers rather than the ancestor pointer the solution tends to fail. Because in that case a bottom up manner will not work, since the pointers can only show the nodes which are left of the current and right of the current one.
Moreover how can you do if at the beginning of the question you only have the node values, but not the positions ? You'll need to track down to find where they are and spent 2 passes to find their exact locations. Only after then you may try to find the common ancestor but with down-pointing pointers it is harder than this implementation. Nice work though :)

Bragaadeesh said...

@Mavi: What you say is correct. As a matter of fact, I have an implementation for this problem without having an ancestor node.

Maulish Soni said...

follow is is efficient one

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

puttyshell said...

http://www.sureinterview.com/shwqst/114001

General idea

1. If the parent node link is given, we can trace each node back to the root. The problem is to check where those two links merge. 2. If it is a binary search tree (BST), we needs to find the node whose branch covers both nodes. Each node in BST has a min and a max that covers some certain range.