CareerCup

distance from node1 to common ancestor + distance from node2 to common ancestor

If it's a bst then there must be one unique path between any two of nodes. the complexity of searching in BST is log(n) .

void Bst::Path(int  &i_source , int  &i_destination ){ // give two node value for searching path
                    node *temp=FindBreak( root , i_source , i_destination );
                     if( temp->i_value == i_source && temp->i_value == i_destination ){
                            std::cout<<temp->i_value<<std::endl;
                    }
                                   Push( temp , i_source );
                                   Push(temp , i_destination);
                                   PrintMap();
}






   
node *Bst::FindBreak( node *temp, int &i_source , int &i_destination ){ // find the breaking node after which source & destination nodes became ( left , righ ) of break point node
	//node *temp=root;
	while ( temp!=NULL ){
		int i_change=0;
		while ( temp->i_value >i_source & temp->i_value>i_destination ){
			std::cout<<"left\n";
			temp=temp->l_child;
                        i_change=1;
		}
		while( temp->i_value <i_source & temp->i_value<i_destination ){
			std::cout<<"Right\n";
			temp=temp->r_child;
                        i_change=1;
		}
		//std::cout<<temp->i_value<<std::endl;
		if ( i_change == 0 ) return temp;
                 FindBreak ( temp , i_source , i_destination);
	
	}
}

void Bst::PrintMap(){
     std::cout<<"The path is -------- \n";
   for ( Track::iterator ii=m_track.begin() ; ii!=m_track.end() ; ii ++ )
                                  std::cout<<ii->first<<"-->";
                                  std::cout<<"END"<<std::endl;
}

void Bst::Push ( node *temp , int &i_search ){
                    while( temp!=NULL ){
                  m_track[ temp->i_value ]=temp->i_value;
                if( temp->i_value == i_search )
                        return ;
                else {
                        m_track[ temp->i_value ]=temp->i_value;
                        if ( temp->i_value > i_search ) temp=temp->l_child;
                        else temp=temp->r_child;
                }
        }
        return ;
 }

Maximum path will be in case when bst is in a form of linked list. So it will be a number of hops (by left or right branch) between these two nodes.

The idea here is to find the lowest common ancestor of the given nodes and then print the path from first given node to second given node through the LCA.

The code is

#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;
 
}

store all ancestors in a stack for both elements(inclusive of themselves) and pop until the ancestors match. then get the path of each to that ancestor

unless you have duplicate nodes there cannot be more than one path between nodes in the BST

// (x, y)
   int maxPath(TreeNode* root, int x, int y)
   {
           if (root == NULL) return INT_MAX; // not found; 
           if (root->data == x) return 1 + distance(root->right, y);
           else if (root->data == y) return 1 + distance(root->left, x);
           else if (root->data < x) return maxPath(root->right, x , y);
           else if (root->data > y) return maxPath(root->left, x, y);
           else return 2 + distance(root->left, x) + distance(root->right, y);  
   }

     int distance(TreeNode* root, int key)
   {
          if (root == NULL) return INT_MAX ; // not found;
          else if (root->val == key) return 0;
          else if (key > root->right) return 1 + distance(root->right, key);
          else return 1 + distance(root->left, key);
   }

int maxPath(int a, int b){
return maxPath(BST.root,a, b);
}

int maxPath(BST node,int a, int b){
if(a<node.val && b<node.val)
return maxPath(node.left,a, b);
else if(a>node.val && b>node.val)
return maxPath(node.right,a, b);

return height1(node,a)+height1(node,b);
}

int height1(BST node, int a){
if(node.val == a)
return 0;
if(node.val<a)
return 1+height1(node.right,a);
return 1+height1(node.left,a);
}

Maximum distance between 2 nodes in a binary tree is nothing but the "diameter of the tree".

Add the depths of both the nodes.