Given a N ary Tree consisting of N nodes, the task is to find the minimum distance from node A to node B of the tree.
Examples:
Input:
1
/ \
2 3
/ \ / \ \
4 5 6 7 8
A = 4, B = 3
Output: 3
Explanation: The path 4->2->1->3 gives the minimum distance from A to B.Input:
1
/ \
2 3
/ \ \
6 7 8
A = 6, B = 7
Output: 2
Approach: This problem can be solved by using concept of LCA(Lowest Common Ancestor). Minimum distance between two given nodes A and B can be found out by using formula –
mindistance(A, B) = dist (LCA, A) + dist (LCA, B)
Follow the steps below to solve the problem:
- Find path from root node to the nodes A and B, respectively and simultaneously store the two paths in two arrays.
- Now iterate until values of both the arrays are same and value just before mismatch is the LCA node value.
- The value just before mismatch is the LCA node value.
- Find distance from the LCA node to node A and B, which can be found with the given steps:
- In first array, iterate from LCA node value and increase count until value of node A is found, which is dist (LCA, A).
- In the second array, iterate from LCA node value and increase count until value of node B is found, which is dist (LCA, B)
- Return the sum of those distances i.e dist (LCA, A) + dist (LCA, B).
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Structure of Nodestruct Node { int val; vector<Node*> child;};// Utility function to create a// new tree nodeNode* newNode(int key){ Node* temp = new Node; temp->val = key; return temp;}bool flag;// Function to get the path// from root to a nodevoid findPath(Node* root, int key, vector<int>& arr){ if (!root) return; arr.push_back(root->val); // if key is found set flag and return if (root->val == key) { flag = 1; return; } // recur for all children for (int i = 0; i < root->child.size(); i++) { findPath(root->child[i], key, arr); // if key is found dont need to pop values if (flag == 1) return; } arr.pop_back(); return;}void findMinDist(Node* root, int A, int B){ if (root == NULL) return; int val = root->val; // vector to store both paths vector<int> arr1, arr2; // set flag as false; flag = false; // find path from root to node a findPath(root, A, arr1); // set flag again as false; flag = false; // find path from root to node b findPath(root, B, arr2); // to store index of LCA node int j; // if unequal values are found // return previous value for (int i = 1; i < min(arr1.size(), arr2.size()); i++) { if (arr1[i] != arr2[i]) { val = arr1[i - 1]; j = i - 1; break; } } int d1 = 0, d2 = 0; // iterate for finding distance // between LCA(a, b) and a for (int i = j; i < arr1.size(); i++) if (arr1[i] == A) break; else d1 += 1; // iterate for finding distance // between LCA(a, b) and b for (int i = j; i < arr2.size(); i++) if (arr2[i] == B) break; else d2 += 1; // get distance val = d1 + d2; cout << val << '\n';}// Driver Codeint main(){ Node* root = newNode(1); (root->child).push_back(newNode(2)); (root->child).push_back(newNode(3)); (root->child[0]->child).push_back(newNode(4)); (root->child[0]->child).push_back(newNode(5)); (root->child[1]->child).push_back(newNode(6)); (root->child[1])->child.push_back(newNode(7)); (root->child[1]->child).push_back(newNode(8)); int A = 4, B = 3; // get min distance findMinDist(root, A, B); return 0;} |
Java
// Java program for the above approachimport java.util.*;public class Main{ // Structure of Node static class Node { public int val; public Node left, right; public Vector<Node> child; public Node(int key) { val = key; left = right = null; child = new Vector<Node>(); } } // Utility function to create a // new tree node static Node newNode(int key) { Node temp = new Node(key); return temp; } static int flag; // Function to get the path // from root to a node static void findPath(Node root, int key, Vector<Integer> arr) { if (root==null) return; arr.add(root.val); // if key is found set flag and return if (root.val == key) { flag = 1; return; } // recur for all children for (int i = 0; i < root.child.size(); i++) { findPath(root.child.get(i), key, arr); // if key is found dont need to pop values if (flag == 1) return; } arr.remove(arr.size()-1); return; } static void findMinDist(Node root, int A, int B) { if (root == null) return; int val = root.val; // vector to store both paths Vector<Integer> arr1 = new Vector<Integer>(); Vector<Integer> arr2 = new Vector<Integer>(); // set flag as false; flag = 0; // find path from root to node a findPath(root, A, arr1); // set flag again as false; flag = 0; // find path from root to node b findPath(root, B, arr2); // to store index of LCA node int j=0; // if unequal values are found // return previous value for (int i = 1; i < Math.min(arr1.size(), arr2.size()); i++) { if (arr1.get(i) != arr2.get(i)) { val = arr1.get(i - 1); j = i - 1; break; } } int d1 = 0, d2 = 0; // iterate for finding distance // between LCA(a, b) and a for (int i = j; i < arr1.size(); i++) if (arr1.get(i) == A) break; else d1 += 1; // iterate for finding distance // between LCA(a, b) and b for (int i = j; i < arr2.size(); i++) if (arr2.get(i) == B) break; else d2 += 1; // get distance val = d1 + d2; System.out.println(val); } public static void main(String[] args) { Node root = newNode(1); (root.child).add(newNode(2)); (root.child).add(newNode(3)); (root.child.get(0).child).add(newNode(4)); (root.child.get(0).child).add(newNode(5)); (root.child.get(1).child).add(newNode(6)); (root.child.get(1)).child.add(newNode(7)); (root.child.get(1).child).add(newNode(8)); int A = 4, B = 3; // get min distance findMinDist(root, A, B); }}// This code is contributed by mukesh07. |
Python3
# Python3 program for the above approach# Structure of Nodeclass Node: def __init__(self, key): self.val = key self.left = None self.right = None self.child = []# Utility function to create a# new tree nodedef newNode(key): temp = Node(key) return tempflag = 0# Function to get the path# from root to a nodedef findPath(root, key, arr): global flag if (root==None): return arr.append(root.val) # if key is found set flag and return if (root.val == key): flag = 1 return # recur for all children for i in range(len(root.child)): findPath(root.child[i], key, arr) # if key is found dont need to pop values if (flag == 1): return arr.pop() returndef findMinDist(root, A, B): global flag if (root == None): return val = root.val # vector to store both paths arr1 = [] arr2 = [] # set flag as false; flag = 0 # find path from root to node a findPath(root, A, arr1) # set flag again as false; flag = 0 # find path from root to node b findPath(root, B, arr2) # to store index of LCA node j=0 # if unequal values are found # return previous value for i in range(min(len(arr1), len(arr2))): if (arr1[i] != arr2[i]): val = arr1[i - 1] j = i - 1 break d1, d2 = 0, 0 # iterate for finding distance # between LCA(a, b) and a for i in range(j, len(arr1)): if (arr1[i] == A): break else: d1 += 1 # iterate for finding distance # between LCA(a, b) and b for i in range(j, len(arr2)): if (arr2[i] == B): break else: d2 += 1 # get distance val = d1 + d2 print(val)root = newNode(1)(root.child).append(newNode(2))(root.child).append(newNode(3))(root.child[0].child).append(newNode(4))(root.child[0].child).append(newNode(5))(root.child[1].child).append(newNode(6))(root.child[1]).child.append(newNode(7))(root.child[1].child).append(newNode(8))A, B = 4, 3# get min distancefindMinDist(root, A, B)# This code is contributed by rameshtravel07. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;// Structure of Nodeclass GFG{ public class Node { public int val; public Node left=null, right=null; public List<Node> child = new List<Node>(); }// Utility function to create a// new tree nodestatic Node newNode(int key){ Node temp = new Node(); temp.val = key; return temp;}static int flag;// Function to get the path// from root to a nodestatic void findPath(Node root, int key, List<int> arr){ if (root==null) return; arr.Add(root.val); // if key is found set flag and return if (root.val == key) { flag = 1; return; } // recur for all children for (int i = 0; i < root.child.Count; i++) { findPath(root.child[i], key, arr); // if key is found dont need to pop values if (flag == 1) return; } arr.RemoveAt(arr.Count-1); return;}static void findMinDist(Node root, int A, int B){ if (root == null) return; int val = root.val; // vector to store both paths List<int> arr1 = new List<int>(); List<int> arr2 = new List<int>(); // set flag as false; flag = 0; // find path from root to node a findPath(root, A, arr1); // set flag again as false; flag = 0; // find path from root to node b findPath(root, B, arr2); // to store index of LCA node int j=0; // if unequal values are found // return previous value for (int i = 1; i < Math.Min(arr1.Count, arr2.Count); i++) { if (arr1[i] != arr2[i]) { val = arr1[i - 1]; j = i - 1; break; } } int d1 = 0, d2 = 0; // iterate for finding distance // between LCA(a, b) and a for (int i = j; i < arr1.Count; i++) if (arr1[i] == A) break; else d1 += 1; // iterate for finding distance // between LCA(a, b) and b for (int i = j; i < arr2.Count; i++) if (arr2[i] == B) break; else d2 += 1; // get distance val = d1 + d2; Console.WriteLine(val);}// Driver Codepublic static void Main(){ Node root = newNode(1); (root.child).Add(newNode(2)); (root.child).Add(newNode(3)); (root.child[0].child).Add(newNode(4)); (root.child[0].child).Add(newNode(5)); (root.child[1].child).Add(newNode(6)); (root.child[1]).child.Add(newNode(7)); (root.child[1].child).Add(newNode(8)); int A = 4, B = 3; // get min distance findMinDist(root, A, B);}}// This code is contributed by SURENDRA_GANGWAR. |
Javascript
<script> // Javascript program for the above approach // Structure of Node class Node { constructor(key) { this.left = null; this.right = null; this.val = key; this.child = []; } } // Utility function to create a // new tree node function newNode(key) { let temp = new Node(key); return temp; } let flag; // Function to get the path // from root to a node function findPath(root, key, arr) { if (root==null) return; arr.push(root.val); // if key is found set flag and return if (root.val == key) { flag = 1; return; } // recur for all children for (let i = 0; i < root.child.length; i++) { findPath(root.child[i], key, arr); // if key is found dont need to pop values if (flag == 1) return; } arr.pop(); return; } function findMinDist(root, A, B) { if (root == null) return; let val = root.val; // vector to store both paths let arr1 = []; let arr2 = []; // set flag as false; flag = 0; // find path from root to node a findPath(root, A, arr1); // set flag again as false; flag = 0; // find path from root to node b findPath(root, B, arr2); // to store index of LCA node let j=0; // if unequal values are found // return previous value for (let i = 1; i < Math.min(arr1.length, arr2.length); i++) { if (arr1[i] != arr2[i]) { val = arr1[i - 1]; j = i - 1; break; } } let d1 = 0, d2 = 0; // iterate for finding distance // between LCA(a, b) and a for (let i = j; i < arr1.length; i++) if (arr1[i] == A) break; else d1 += 1; // iterate for finding distance // between LCA(a, b) and b for (let i = j; i < arr2.length; i++) if (arr2[i] == B) break; else d2 += 1; // get distance val = d1 + d2; document.write(val); } let root = newNode(1); (root.child).push(newNode(2)); (root.child).push(newNode(3)); (root.child[0].child).push(newNode(4)); (root.child[0].child).push(newNode(5)); (root.child[1].child).push(newNode(6)); (root.child[1]).child.push(newNode(7)); (root.child[1].child).push(newNode(8)); let A = 4, B = 3; // get min distance findMinDist(root, A, B);// This code is contributed by decode2207.</script> |
Output
3
Time complexity: O(N).
Auxiliary Space: O(N).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
