CareerCup

- Consider the two paths as two linked lists
- find the length of both the lists and get the difference in length
- move the pointer of longer list by the difference and add every node to the path
- move pointers to both the lists till they meet and add nodes to respective paths
- if the meeting point is root add root to both the paths
- display the paths

void printPath (Node node1, Node node2) {
          if(node1 == null && node2 == null)
              return ;
         
         int len1 = 0, len2 = 0;
      
         Node temp = node1;
         
         while(temp != null) {
             temp = temp.parent; 
            ++len1;
         }
         
       temp = node2;

       while(temp != null) {             
              temp = temp.parent; 
             ++len2;
       }

        StringBuffer path1 = new StringBuffer();
        StringBuffer path2 = new StringBuffer();

        if(len1 > len2 ) {              
            for(int i = 0; i < len1 - len2 ; i++) {
                  
                  path1.append(node1.data);
                 node1 = node1.parent;
               }                  
         }else {

               for(int i = 0; i < len2 - len1 ; i++) {
                  
                  path2.append(node2.data);
                 node2 = node2.parent;
               }                   
          }
          
         while(node1 != node2) {
                path1.append(node1.data);
                path2.append(node2.data);     
                node1 = node1.parent;
                node2 = node2.parent;
          }
         
        if(node1 == root) {
                 path1.append(root.data);
                 path2.append(root.data):
        }
        
       System.out.println(path1.toString());
       System.out.println(path2.toString());

 }

Find the LCA of the two nodes.
- If the LCA is the root, then it means that both the nodes have unique path to the root. Print both the paths.

- Else, it means that the nodes have unique path till the LCA node. Print the paths for each of these nodes till the LCA

First store a pointer to first node. Then keep traversing the first node's parent till we hit the root. Note whether we encounter the second node along the way with the "encountered" variable. If we encountered the second node along the way, then we already printed the path from the second node to the root. Otherwise, keep traversing the second node's parent pointer till we either hit the root or encounter the original first node along the way. Advantage of this is that we only traverse both paths once, and we aren't using any additional data structure.

(Didn't really test this code though)

static void findRoot(Node n, Node n2) {
  boolean encountered = false;
  Node tmp = n;
  System.out.println("FIRST");
  while(n != null) {
    if(n == n2)
      encountered = true;
    System.out.println(n.value);
    n = n.parent;
  }

  System.out.println("SECOND");
  while(!encountered && n2 != null) {
    System.out.println(n2.value);
    n2 = n2.parent;
    if(n2 == tmp)
      encountered = true;
  }
}

What about storing the path's of both the tree in two HashMap and find if a common node exists....if yes then print the hashMap till that node other wise print the whole HashMap

question not very clear..
what I understand from it.is
it will be a complete binary tree and then from any two nodes ,we can find the shortest path
from the root and can eliminate the common path...

i dont know if it holds correct.

I really do not understand what is the meaning of printing path here. My understanding is printing the value or the node pointer.
if so code goes here

printpath(node * node1, node* node2)
{
if(node1 == NULL || node2 == NULL)
{// reached parent
return;
}
if(node1 == node2)
{
// now both the nodes have same parent so stop printing
return;
}
print node1;
print node2;
printpath(node1-> parent, node2->parent);
}