Solution For Find Closest Node To Given Two Nodes

Problem Statement:

You are given a graph consisting of n nodes represented by an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi.

You are also given two different nodes start and end.

Return the closest node to start that is directly connected to end. Note that there can be multiple answers for this question.

It is guaranteed that there exists a path between start and end.

Approach:

We can use BFS to find the shortest path from start to end, then we can backtrace this path to find the closest node directly connected to end.

First, we will build an adjacency list to represent the graph.

Then, we will run BFS from start node and keep track of the distance of each node from start.

Once we reach the end node, we will backtrace using the parent array to find the closest nodes that are directly connected to end.

Solution:

Here is the Python implementation of the above approach:

from collections import defaultdict
from queue import Queue

class Solution:
def findClosest(self, n: int, edges: List[List[int]], start: int, end: int) -> int:
# build adjacency list
adj_list = defaultdict(list)
for u, v in edges:
adj_list[u].append(v)
adj_list[v].append(u)

    # BFS to find shortest path from start to end
    visited = [False] * n
    parent = [-1] * n
    distance = [-1] * n
    q = Queue()
    q.put(start)
    visited[start] = True
    distance[start] = 0

    while not q.empty():
        u = q.get()
        for v in adj_list[u]:
            if not visited[v]:
                visited[v] = True
                parent[v] = u
                distance[v] = distance[u] + 1
                q.put(v)
                # termination condition
                if v == end:
                    return self.closestNode(adj_list, parent, end)

def closestNode(self, adj_list, parent, end):
    # backtrace path from end to start
    nodes = []
    node = end

    while node != -1:
        nodes.append(node)
        node = parent[node]

    # find closest node directly connected to end
    min_distance = float('inf')
    closest_node = -1

    for node in nodes:
        for neighbor in adj_list[node]:
            if neighbor in nodes:
                if distance := abs(neighbor - node) < min_distance:
                    min_distance = distance
                    closest_node = neighbor

    return closest_node

The time complexity of the above solution is O(n) for building the adjacency list, O(n) for BFS, and O(n) for backtracing the path. Therefore, the overall time complexity is O(n).

The space complexity is O(n) for the adjacency list, visited, parent, and distance arrays. Therefore, the overall space complexity is O(n).

Step by Step Implementation For Find Closest Node To Given Two Nodes

Given a binary search tree and two values. Find the closest node to the given two values.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode findClosestNode(TreeNode root, int k1, int k2) {
        // closest node to k1 is the node with the smallest difference in value
        TreeNode closestToK1 = root;
        int minDiff = Math.abs(root.val - k1);
        
        // closest node to k2 is the node with the smallest difference in value
        TreeNode closestToK2 = root;
        int minDiff2 = Math.abs(root.val - k2);
        
        // iterate through the tree to find the nodes closest to k1 and k2
        while (root != null) {
            // update minDiff if root.val is closer to k1
            if (Math.abs(root.val - k1) < minDiff) {
                minDiff = Math.abs(root.val - k1);
                closestToK1 = root;
            }
            
            // update minDiff2 if root.val is closer to k2
            if (Math.abs(root.val - k2) < minDiff2) {
                minDiff2 = Math.abs(root.val - k2);
                closestToK2 = root;
            }
            
            // if root.val is equal to k1 or k2, we can return root
            if (root.val == k1 || root.val == k2) {
                return root;
            }
            
            // if k1 is less than root.val, go left
            // if k1 is greater than root.val, go right
            if (k1 < root.val) {
                root = root.left;
            } else {
                root = root.right;
            }
        }
        
        // if the closest node to k1 is also the closest node to k2, return that node
        if (closestToK1 == closestToK2) {
            return closestToK1;
        }
        
        // otherwise, find the lowest common ancestor of k1 and k2
        TreeNode lca = findLCA(root, k1, k2);
        
        // if the lowest common ancestor is equal to k1 or k2, return the LCA
        if (lca.val == k1 || lca.val == k2) {
            return lca;
        }
        
        // otherwise, return the node with the smallest difference in value from the LCA
        if (Math.abs(lca.val - k1) < Math.abs(lca.val - k2)) {
            return closestToK1;
        } else {
            return closestToK2;
        }
    }
    
    public TreeNode findLCA(TreeNode root, int k1, int k2) {
        // base case: if root is null, return null
        if (root == null) {
            return null;
        }
        
        // if k1 is equal to root.val or k2 is equal to root.val, return root
        if (root.val == k1 || root.val == k2) {
            return root;
        }
        
        // otherwise, recurse on root.left and root.right
        TreeNode left = findLCA(root.left, k1, k2);
        TreeNode right = findLCA(root.right, k1, k2);
        
        // if both left and right are not null, root is the LCA
        if (left != null && right != null) {
            return root;
        }
        
        // if left is not null, return left
        if (left != null) {
            return left;
        }
        
        // if right is not null, return right
        if (right != null) {
            return right;
        }
        
        // otherwise, return null
        return null;
    }
}

This is a Python implementation of a breadth-first search algorithm that finds the closest node to the given two nodes.

def find_closest_node(graph, node1, node2):

# keep track of the nodes we've visited
visited = set()

# create a queue for storing the nodes to visit
queue = []

# add the starting node to the queue
queue.append(node1)

# while the queue is not empty
while queue:

# get the next node from the queue
node = queue.pop(0)

# if the node has not been visited
if node not in visited:

# mark the node as visited
visited.add(node)

# if the node is the goal node, we're done
if node == node2:

# return the path
return path

# get the node's neighbors
for neighbor in graph[node]:

# add the neighbor to the queue
queue.append(neighbor)

# if we get here, then there is no path from node1 to node2
return None

Given a binary tree, find the closest node to the given two nodes.

function findClosestNode(node1, node2) {
  // TODO: your code here
}

There are many possible solutions to this problem. One approach would be to use a data structure like a binary search tree or a hash table to store the nodes in the tree. Then, we could use a breadth-first search or a depth-first search to find the path between the two nodes. Finally, we could use a heuristic like the Manhattan distance to find the closest node.

Given a binary tree, find the closest node to the given two nodes.

// find the path from the root to each node 
// compare the paths to find the closest node 

public TreeNode FindClosestNode(TreeNode root, TreeNode n1, TreeNode n2) 
{
    List path1 = new List(); 
    List path2 = new List(); 
  
    // find path from root to n1 and store it in path1 
    // find path from root to n2 and store it in path2 
  
    int i = 0; 
    while (i < path1.size() && i < path2.size()) 
    { 
        // if the nodes are not equal, then we have found the closest node 
        if (path1[i] != path2[i]) 
            break; 
        i++; 
    } 
  
    // return the previous node since we need the closest node 
    return path1[i-1]; 
}