hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Find Closest Node to Given Two Nodes


  • Approach:

    1. From the given edges list we can build a graph.

    2. We will be starting BFS from node1.

    3. We will calculate the distance of each node starting from node1.

    4. Again we will start BFS from node2.

    5. And we will calculate the distance of each node starting from node2.

    6. Now for each node starting from 0 to N-1, we will find the max calculated distance.

    7. From those max calculated distances, we will find out the minimum one.

    8. And return the node number at the end.


  • Time and Space Complexity:

      • Time Complexity: O(N)

      • Space Complexity: O(N)


Code [C++]

class Solution {

public:


// As the given graph is a tree, the following BFS will work.

void bfs(vector<int> & graph, vector<int> & distance, int src){

queue<int>Q;

distance[src] = 0;

while(true){

int next = graph[src];

if(next == -1 || distance[next] != -1){

break;

}

distance[next] = distance[src] + 1;

src = next;

}

}


int closestMeetingNode(vector<int>& edges, int node1, int node2) {

int n = edges.size();

vector<int>dist_node1(n, -1);

vector<int>dist_node2(n, -1);

bfs(edges, dist_node1, node1);

bfs(edges, dist_node2, node2);


int minValue = n, ans = -1;

for(int i=0; i<n; i++){

if(dist_node1[i] == -1 || dist_node2[i]==-1) continue;

int max_dist = max(dist_node1[i], dist_node2[i]);

if(max_dist < minValue){

minValue = max_dist;

ans = i;

}

}

return ans;

}

};