CareerCup

In order to find the shortest path between any two nodes you have to find the common parent between them that is the least common ancestor.
As it is not a binary search tree so just do a level order traversal and store them in a array then the indexing of the array would be such that for any node of array index n you will have parent at index (n-1)/2 .So for any two nodes just check if they have the same parent. If they have then it is the least common ancestor and the path length is 2 from 1st node to parent and then from parent to second node. If not then iterate upwards until you get a common parent and also increment a path count. I have also uploaded the code for it below.
This is the code for finding least common ancestor in a binary tree:
a. Store the nodes by doing a normal level order traversal
b. And then find the common parent of the node in the array

#include <stdio.h>
#include <conio.h>
#include <malloc.h>
typedef struct tree tree_t;
struct tree
{
	int data;
	tree_t *left;
	tree_t *right;
};
tree_t *newNode(int data)
{
	tree_t *n=(tree_t *)malloc(sizeof(tree_t));
	n->data=data;
	n->left=n->right=NULL;
	return n;
}
typedef struct queue q_t;
struct queue
{
	int front;
	int rear;
	int size;
	tree_t **array;
};
q_t *newQueue(int size)
{
	q_t *q=(q_t *)malloc(sizeof(q_t));
	q->front=q->rear=0;
	q->array=(tree_t **)malloc(q->size*sizeof(tree_t *));
	return q;
}
void enq(q_t *q,tree_t *t)
{
	q->array[q->rear++]=t;
}
tree_t *dequeue(q_t *q)
{
	q->front++;
	return q->array[q->front-1];
}
void printLca(int arr[],int *n,int n1,int n2)
{
	int i,parent1,parent2;
	int path=2;//path is obviously 2 if both the parents are same 
		
	for(i=0;i<*n;i++)
	{
		if(arr[i]==n1)
		{
			parent1=(i-1)/2;
		}
		else if(arr[i]==n2)
		{
			parent2=(i-1)/2;
		}
	}
	if(parent1==parent2)//if both the parents are same then it is the least common ancestor
	{
		printf(" The least common ancestor is %d and shortest path is %d",arr[parent1],path);
	}
	else//iterate until you find a common parent a parent for node n is (n-1)/2 its floor value and also increment the path
	{
		
		while(parent1!=parent2)
		{
			if(parent1<parent2)
			{
				parent2=(parent2-1)/2;
				path=path+1;
			}
			else if(parent2<parent1)
			{
				parent1=(parent1-1)/2;
				path=path+1;
			}
		}
		printf(" The least common ancestor is %d and shortest path is %d",arr[parent1],path);
	}
	
}
void lca(tree_t *t,int arr[],int n1,int n2,int *index)
{
	q_t *q=newQueue(20);
	tree_t *temp=t;
	while(temp)
	{
		arr[*index]=temp->data;
		(*index)++;
		if(temp->left)
			enq(q,temp->left);
		if(temp->right)
			enq(q,temp->right);
		temp=dequeue(q);
	}
	printLca(arr,index,n1,n2);
}
int main()
{
	tree_t *t=newNode(1);
	t->left=newNode(2);
	t->left->left=newNode(4);
	t->left->left->left=newNode(8);
	t->left->left->right=newNode(10);
	t->left->right=newNode(5);
	t->left->right->right=newNode(9);
	t->right=newNode(3);
	t->right->left=newNode(6);
	t->right->right=newNode(7);
	int arr[30],index=0;
	lca(t,arr,8,6,&index);
}

We can perform a Breadth First Search, from the node of the tree to any one of the two given nodes (say node1). This can be done in linear O(n) time. Also, we store this path, as an array of node numbers (assuming we number the nodes from 0 (root) to n-1 (last) leaf node), that form the path. (this array is sorted)

We then start moving up (using parents) from the other node (node2), towards the root. Now, while moving, whenever we find a node, that is in the array of node1's path upto root, we stop moving. Now we merge both the paths to get shortest path between them.

hmm yes may be its an binary tree but the idea is same ,we need to find the LCA and then print the path through LCA

main( )
  {
    ...
    findpath()
  }

  
  findpath(node *a,node *b,node *root)
  {
    stack s1,s2;
    // Get the path of node a from root in a stack
    find(a,root,s1); 
 
    // Get the path of node b from root in a stack
    find(b,root,s2);
 
    //using stack s1,s2 print the path
 }

  
  find(a,root,stack s)
  {
    if(root == a)
    {
      return 1;
    }
    
    if(root == NULL)
    {
      return 0;
    }
 
    s.push(root);   
    if(find(a,root->left,s) || find(a,root->right,s))
    {
       return 1;
    }
    else
    {
         s.pop( );
         return 0;
      }
   }

a. Find the LCA, Can use RMQ if we can keep array or can use recursive algorithm.
b. Add distance of the two nodes from LCA.

a. Find the LCA, Can use RMQ if we can keep array or can use recursive algorithm.
b. Add distance of the two nodes from LCA.

use BFS

Simple:
1. First check whether both the nodes exist in the tree? (skipping for simplicity)
2. Find the lowest common ancestors of both the nodes.
3. Trace path to node1 from LCA node.
4. Trace path from node2 to LCA node.

Let node1.val = val1
and node2.val = val2

node* LowestCommonAncestor(node *ptr, int val1, int val2) 
{
	if (!ptr) 
		return NULL;
	if (ptr->getData() == val1 || ptr->getData()== val2) 
		return ptr;
	node *left  = LowestCommonAncestor(ptr->getLeftChild(), val1, val2);
	node *right = LowestCommonAncestor(ptr->getRightChild(), val1, val2);
	
	if (left && right) 
		return ptr;  
		
	if(left)
		return left;
	else
		return right;
}

For tracing path to the node:
LCA = LowestCommonAncestor(root,item1,item2)
trace(LCA,item1);
trace(LCA,item2);

int equal=0;
void trace(node *r,int item)
{
      if(equal==1)
            return;

      if(r->data==item)
            equal=1;
      if(r!=NULL)
      {
            trace(r->left,item);
            trace(r->right,item);
            if(equal==1)
                  cout<<"  "<<r->data;
      }
}

If I am not wrong, in a tree for any two distinct vertex there exists a unique path simple path.
The question says ''Find the shortest distance b/w any two nodes in a binary tree".
But if there exists only one path then how can shortest path be found(Only if there exists at-least two path then we can speak about Shortest Path).
FYI:
The definition of tree from wiki:
A tree is an undirected simple graph G that satisfies any of the following equivalent conditions:
G is connected and has no cycles.
G has no cycles, and a simple cycle is formed if any edge is added to G.
G is connected, but is not connected if any single edge is removed from G.
G is connected and the 3-vertex complete graph K_3 is not a minor of G.
Any two vertices in G can be connected by a unique simple path.

vgeek ... What is the time complexity of your code ? Is it better than O(n). If so then we can use simply BFS that would give the shortest path in O(n) time

int nodeDistance(node *new_node, int n1, int n2){
node *save;
int count = 0, temp = 0;
if(n1 > n2){
temp = n1;
n1 = n2;
n2 = temp;
}
while(n1 < new_node->val && n2 < new_node->val){
new_node = new_node->left;
}
while(n1 > new_node->val && n2 > new_node->val){
new_node = new_node->right;
}

save = new_node;
while(n1 != new_node->val){
if(n1 < new_node->val){
new_node = new_node->left;
count++;
}
else if(n1 > new_node->val){
new_node = new_node->right;
count++;
}
}
new_node = save;
while(n2 != new_node->val){
if(n2 < new_node->val){
new_node = new_node->left;
count++;
}
else if(n2 > new_node->val){
new_node = new_node->right;
count++;
}
}
return count;

}

Just need to find the path from node1 to node 2 throught the LCA of both nodes.

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string.h>
 
 
using namespace std;
 
struct node {
     int data;
struct node *left;
struct node *right;
};
 
void printPath(int num,struct node *LCA)  {
    if(num==LCA->data)  {
        cout<<LCA->data<<" ";
        return;
    }
    
    struct node *temp=LCA;
    if(num<LCA->data)
        LCA=LCA->left;
    else
        LCA=LCA->right;
        
    printPath(num,LCA);
    cout<<temp->data<<" ";
    
}
 
 
void findMaxPath(int num1,int num2,struct node *root) {
    struct node *num1LCA=root;
    struct node *num2LCA=root;
    struct node *LCA=root;
    
    while(num1LCA==num2LCA) {
        if(num1 < num1LCA->data)    
            num1LCA=num1LCA->left;
        else
            num1LCA=num1LCA->right;
            
        if(num2<num2LCA->data)
            num2LCA=num2LCA->left;
        else
            num2LCA=num2LCA->right;
            
        if(num1LCA==num2LCA)
            LCA=num1LCA;
    }
    
    cout<<"Path from node1 to root\n";
    printPath(num1,LCA);
    cout<<"\nAnother path starting from node 2 to root\n";
    printPath(num2,LCA);
    return;
}
 
// FUNCTION TO INSERT NODES IN THE BINARY TREE
void insertNode(struct node **root,int data)  {
 
    // CREATES THE ROOT NODE
if(*root==NULL)  {
 (*root)=(struct node*)malloc(sizeof(struct node));
 (*root)->data=data;
 (*root)->left=NULL;
 (*root)->right=NULL;
        return;
}
    
// FOR CREATION OF OTHER NODES
if(data < (*root)->data) {
 insertNode((&(*root)->left),data);
}
else    {
 insertNode((&(*root)->right),data);
}
return;
}
 
// DRIVER FUNCTION
int main()  {
 
struct node *root=NULL;
 
// TAKES THE INPUT FOR INSERTION
do  {
 int data;
 scanf("%d",&data);
 if(data!=-1)    {
 insertNode(&root,data);
 }
 else    {
break;
 }
}while(1);
 
findMaxPath(10,14,root);
 
 
return 0;
 
}

It is better if you could add more comments to explain the algorithm.