Find the nearest leaf node from given node in binary tree

Question

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 ??

Answer 1

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.

Answer 2

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.