Q:

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

mahmoud2506
Save to bookmark
|
2022-04-30
|
  245 
0

Minimum distance between two given nodes of a Binary Tree

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

Node values are unique.

Example:

Minimum distance between two given nodes of a Binary Tree

Let the two nodes to be 9 and 2, their min distance is 3, In case of 4 and 3 their min distance is 2.

C++ programming, Interview questions, C++ programming Interview-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-04-30
need an explanation for this answer? contact us directly to get an explanation for this answer

One naïve idea can be searching for either of the nodes using BFS. Once either of the nodes is found, corresponding node is marked. We start searching for the other node incrementing distance. But one problem is result always is not guaranteed to be minimum.

Rather what actually should come to your mind is what can be closest node for both the target nodes (distance between those nodes that are to be found). The answer will be lowest common ancestor. So, we actually need to find the lowest common ancestor of two target nodes. Then, we can think the LCA to be root and the target nodes exist in two different branches. (Example 1)

Or there can be situation that both the target nodes exists on same root to leaf path that means one of the two target nodes itself is LCA. (Example 2)

However rest of our job is two find distance of respective target nodes from the LCA.

Let the distances to be distance1 and distance2 respectively.

Then the minimum distance between the two target nodes will be = distance1+distance2

How to find LCA?

Can be done using preorder traversal.

Pre-requisite:

Tree root, target node data values a, b

    FUNCTION LCA (root, a, b)
        //base case
        IF(!root)
            return NULL;

        IF(root->data==a || root->data==b) //it ensures to root to be LCA
            return root;

        Node* l=findlowestancestor(root->left,a,b);
        Node* r=findlowestancestor(root->right,a,b);

        if(l && r) //this can only happen incase of LCA be root
            return root;

        return (l==NULL ?r:l); //NOT NULL one between l and r which contains LCA node
    END FUNCTION

After finding the LCA we compute the distance separately for two nodes. This can be done by level order traversal finding number of levels between target node and root (LCA).

Example with explanation:

Example - Minimum distance between two given nodes of a Binary Tree

Example 1:

    Target nodes:
    9 and 2

    LCA:
    Node with value 5
    Distance1: //distance between 5 and 9
    1
    Distance2: //distance between 5 and 2
    2

    Their min distance is 1+2=3

Example 2:

    Target nodes: 
    4 and 3

    LCA:
    Node with value 4 (first target node itself)
    Distance1: //distance between 4 and 4
    0
    Distance2: //distance between 4 and 3
    2

    Their min distance is 0+2=2

C++ implementation:

#include <bits/stdc++.h>
using namespace std;

class Node{ //tree node
	public:
	int data;
	Node *left;
	Node *right;
};

//finding lowest common ancestor
Node* findlowestancestor(Node* root,int a,int b){
	if(!root)
		return NULL;

	if(root->data==a || root->data==b)
		return root;

	Node* l=findlowestancestor(root->left,a,b);
	Node* r=findlowestancestor(root->right,a,b);

	if(l && r)
		return root;

	return (l==NULL ?r:l);
}   

//finding distance between root(LCA) and target node
int height(Node* root, int a){
	//base cases
	if(root==NULL)
		return 0;

	if(root->data==a)
		return 0;

	//level order 
	queue<Node*> q;
	q.push(root);
	q.push(NULL);
	int height=0;
	while(!q.empty()){
		Node* temp=q.front();
		q.pop();
		
		if(!temp){
			if(!q.empty()){
				q.push(NULL);
			}
			height++;
		}
		else{
			if(temp->data==a)
				return height;
			if(temp->left)
				q.push(temp->left);
			if(temp->right)
				q.push(temp->right);
		}
	}

	return height;
}

int findDist(Node* root, int a, int b)
{
	Node* t=findlowestancestor(root,a,b); 
	int p=height(t,a);
	int q=height(t,b);

	return p+q;
}

//creating new nodes
Node* newnode(int data){  
	Node* node = (Node*)malloc(sizeof(Node)); 
	node->data = data; 
	node->left = NULL; 
	node->right = NULL; 
	return(node); 
} 

int main() { 
	//**same tree is builted as shown in example**
	cout<<"tree in the example is build here"<<endl;
	//building the tree like as in the example
	Node *root=newnode(8); 
	root->left= newnode(5); 
	root->right= newnode(4); 
	root->right->right=newnode(1);
	root->right->right->left=newnode(3);
	root->left->left=newnode(9); 
	root->left->right=newnode(7);
	root->left->right->right=newnode(2);


	cout<<"Example 1......"<<endl;
	cout<<"Miniimum distance between 9 and 2\n";
	cout<<findDist(root,9,2)<<endl;
	cout<<"Example 2......"<<endl;
	cout<<"Miniimum distance between 4 and 3\n";
	cout<<findDist(root,4,3);
	return 0; 
}

Output

 

tree in the example is build here
Example 1......
Miniimum distance between 9 and 2
3
Example 2......
Miniimum distance between 4 and 3
2

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Interview C++ coding problems/challenges | tree
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Find the k-th smallest element in a given binary s... >>
<< Given a binary tree, where every node value is a n...