Minimum distance between two given nodes of Binary Tree

In this article, we will be discussing about the problem "Minimum distance between two given nodes of a Binary Tree" in detail. This involve the concept of lowest common ancestor.

Contents:

1. Introduction
2. Optimized approach
3. Implementation
4. Code Explanation
5. Time and Space Complexity Analysis

Introduction:

In this problem at OpenGenus, we are going to find the minimum distance between two given nodes of a given binary tree. The distance between two nodes is the minimum number of edges to be travelled to reach one node from another. we are not given with any parent pointer and the given two nodes will always present in the binary tree.

Example 1:

Suppose in the above example we are given 7 as the first node and 9 as the second node. so the minimum distance between the given two nodes will be 3 as we have to move 1 edge(2->7) from node 2 to node 7 and 2 edges(2->5->9) in moving from node 2 to node 9. so total edge covered will be 3.

Example 2:

Suppose in the above example we are given 3 as the first node and 7 as the second node. so the minimum distance between the given two nodes will be 2 as we have to move 2 edge(3->6->7) from node 3 to node 7. so total edge covered will be 2.

Optimized Approach:

In the optimized approach, first we will find the lowest common ancestor of the given two nodes. After finding the lowest common ancestor of these two nodes, we will find the distances lowest common ancestor from the given two nodes seperately and then we will add both the distances and return it.

Algorithm:

1. Find the lowest common ancestor of the given two nodes.
2. Find distance of first given node from that lowest common ancestor using any recursive traversal method (Here we will be using inorder traversal).
3. Find distance of second given node from that lowest common ancestor using same function.
4. Return sum of both the distances calculated above.

Implementation:

import java.util.*;
class Node
{
   int data;
   Node left;
   Node right;
   Node nextRight;
   Node(int data)
   {
      this.data = data;
      left=null;
      right=null;
      nextRight = null;
   }
 }
  class Main {
    public static int findDist(Node root, int a, int b) 
    {
        // Your code here
        Node lc = lca(root,a,b);
        int dis1 = findDis(lc,a,0);;
        int dis2 = findDis(lc,b,0);;
        return (dis1+dis2);
    }
    
    public static Node lca(Node root, int n1, int n2)
    {
        if(root==null || root.data==n1 || root.data==n2)
        {
            return root;
        }
        Node path1 = lca(root.left,n1,n2);
        Node path2 = lca(root.right,n1,n2);
        if(path1 == null)
        {
            return path2;
        }
        else if(path2 == null)
        {
            return path1;
        }
        else
        {
            return root;
        }
        
    }
    
    public static int findDis(Node root,int n,int d)
    {
        if(root==null){
            
            return -1;
        }
        
        if(root.data==n){
            return d;
        }
        
        
        int left = findDis(root.left,n,d+1);
        if(left!=-1){
            return left;
        }
        return findDis(root.right,n,d+1);
            
    }
           
    public static void main(String args[])
    {
 
        /* Constructed binary tree is
             10
            /  \
          8     2
         /
        3
        */
        Node root = new Node(10);
        root.left = new Node(8);
        root.right = new Node(2);
        root.left.left = new Node(3);

        System.out.println(findDist(root,3,8));
     }
}

Code Explanation:

1. We are creating a function findDist() and pass the root node and two integer value as a parameter in this.
2. This function will first call the function lca() and find the lowest common ancestor of the given two nodes values. If you don't know how to find the lowest common ancestor of two nodes in a binary tree you can refer to this article https://iq.opengenus.org/lowest-common-ancestor-in-binary-tree/
3. After finding the lowest common ancestor we will find the distance of both the given nodes from their lowest common ancester by using the dis() function and return sum of their distances.

Explanation of dis() function:

1. We are creating a function dis() which will calculate the distance of a node from its ancestor. we will pass the ancestor node, the node value from which we want to calculate the distance and a integer value d for calculating the distance as a parameter in this.
2. In this function we will recursively traverse the binary tree with the ancestor node as the root node in preorder manner i.e, first we will traverse the root then its left subtree and at last its right subtree.
3. If the root is equals to null then we will return -1.
4. If the value of root node is equals to the value of node from which we want to calculate distance then we will return the variable d.
5. If the current node value is not equals to the value of node from which we want to calculate distance, then we will call the dis() function for the left subtree and increment the value of d by 1.
6. If we don't find the node that we are looking for in the left subtree function call or the left subtree function call returns -1, then we will call the function call for the right subtree.

Time and Space Complexity Analysis:

The time complexity of the above solution will be O(N),where N is total number of nodes in the binary tree. As in the above approach we are finding the lowest common ancestor of the given two nodes which will take O(N) time and then we are finding the distance of both nodes from their lowest common ancestor by using the function dis() which will take 2N time. Since the function dis() is traversing the whole binary tree one time, so it will take N time. Therefore overall complexity of the above solution will be N + 2N = O(3N) which is equivalent to O(N).
The space complexity of the above solution will be O(H), where H is the maximum height of the binary tree.

With this article at OpenGenus, you must have the complete idea of solving this problem "Minimum distance between two given nodes of a Binary Tree".