Given a binary tree (not necessarily a binary search tree ) with root node and a particular node, how to find a leaf node which is nearest to the given node ??
Is there any specific algorithm or modification of existing algorithm for this problem ??
1
votes
3 Answers
2
votes
This is a very typical graph traversal problem. You can use Dijkstra's Algorithm to traverse the graph and find the shortest route to a destination.
We use Dijkstra's and not A* in this case because we do not know what our destination is. If you have played Starcraft, this is (almost certainly) what they used for an worker to find the nearest mineral supply or nearest vehicle that needs repaired.
2
votes
Check this link. The idea is to traverse the given tree in preorder and keep track of ancestors in an array. When we reach the given key, we evaluate distance of the closest leaf in subtree rooted with given key. We also traverse all ancestors one by one and find distance of the closest leaf in the subtree rooted with ancestor. We compare all distances and return minimum.
0
votes
If the assumption that a node maintains back link to its parent node is true then doing a BFS will suffice. The idea is first to get to the node of interest, then conduct BFS on its children and its parent links (each parent link will then do BFS on its children exluding the ones that you already visited and its parent). You maintain minimum distance from node of interest to the leaf (MinDistance) and don't do further BFS traversal on the non leaf nodes at a distace >= MinDistance
