CareerCup

first ask the interviewer how to define the order of the leaves

Lets say we call the order to be the dfs traversal order. Then things are quite easy.
First find all the leafs and then using DP things can be done, isnt it?

I meant always LEFT DFS traversal. :)

map<int,int>container;
void getLeafdata(node * ptr)
{
   // Visit the left subtree
   if(ptr->left != 0)
	printLeaf(ptr->left);
   // Visit the right subtree
   if(ptr->right != 0)
	printLeaf(ptr->right);
   // If its leaf then, push the value in container, for future reference.
   if(ptr->left == 0 && ptr->right == 0)
   {
       // push it into map and increase the counter value by 1.
       container[ptr->value]++;
   }
}

void findLongest()
{
    // traverse the container map and look for the highest value.
    // finally print up the highest value.
}

it can be visualized as 2 linked lists with a common node. trace the path of each of the nodes from the root and store it as a stack.

next use the stack as a queue with the top most being the first element.
next find the length of both the queues and then iterate on the longer one so that both point at the length now equals the shorter one.

then search for the common node