Home » Interview coding problems/challenges

Minimum distance between two given nodes of a Binary Tree

In this article, we are going to see how to find distance between any two nodes in a binary tree? This problem has been featured in the interview round of Amazon. Submitted by Radib Kar, on March 28, 2019

Problem statement

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

Node values are unique.

Example

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.

Solution

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).

Explanation with example

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