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

**Example with explanation:**

**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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.

Learn PCB Designing: PCB DESIGNING TUTORIAL