Minimum distance between two given nodes of a Binary Tree

PROBLEM :

Given a binary tree and two node values your task is to find the minimum distance between them.
Example :


Input:
The task is to complete the fuction findDist which takes 3 argument, the  root of the  Binary Tree and two node values a and b .
There are multiple test cases. For each test case, this method will be called individually.

Output:
The function should return min distance between two node values .

Constraints:
1 <=T<= 30
1 <=Number of nodes<= 100
1 <=Data of a node<= 1000

Example:
Input
1
2
1 2 L 1 3 R
2 3

Output
2

In above example there is one  test case which represent a tree with 3 nodes and 2 edges where root is 1, left child of 1 is 2 and right child of 1 is 3.

--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------

/* A binary tree node
struct Node
{
    int data;
    struct Node* left, * right;
}; */

/* Should return minimum distance between a and b
   in a tree with given root*/
 
Node * LCA(Node*  ,int  ,int  ) ;
int distance(Node *,int,int ) ;
 
int findDist(Node* root, int a, int b)
{
    if(root==NULL)
        return 0 ;
       
    Node *ROOT ;
    ROOT=LCA(root,a,b) ;
   
    int l1,l2 ;
    l1=distance(ROOT->left,a,b) ;
    l2=distance(ROOT->right,a,b) ;
   
    return l1+l2 ;
}

Node * LCA(Node* root ,int n1 ,int n2 )
{
    if(root==NULL)
        return root ;
       
    if(root->data==n1)
        return root ;
    if(root->data==n2)
        return root ;
       
    Node *L,*R ;
    L=LCA(root->left,n1,n2) ;
    R=LCA(root->right,n1,n2) ;
   
    if(L&&R)
        return root ;
       
    return (L!=NULL)?L:R ;
}

int distance(Node *root,int ele1,int ele2)
{
    if(root==NULL)
        return 0 ;
    int n1,n2 ;
    if(root->data==ele1||root->data==ele2)
        return 1 ;
 
    n1=distance(root->left,ele1,ele2) ;
    if(n1)
        return n1+1 ;
    n2=distance(root->right,ele1,ele2) ;
    if(n2)
        return n2+1 ;
 
}

---------------------------------------------------------------------------------

Comments

Popular posts from this blog

Count ways to N'th Stair(Order does not matter)

Replace all ‘0’ with ‘5’ in an input Integer

Chocolate Distribution Problem

Remove characters from the first string which are present in the second string

Primality Test ( CodeChef Problem code: PRB01 )