Given a binary tree, and two node values your task is to find the minimum distance between them
All Answers
total answers (1)
Severity: 8192
Message: str_replace(): Passing null to parameter #3 ($subject) of type array|string is deprecated
Filename: libraries/Filtered_db.php
Line Number: 23
total answers (1)
One naïve idea can be searching for either of the nodes using BFS. Once either of the nodes is found, corresponding node is marked. We start searching for the other node incrementing distance. But one problem is result always is not guaranteed to be minimum.
Rather what actually should come to your mind is what can be closest node for both the target nodes (distance between those nodes that are to be found). The answer will be lowest common ancestor. So, we actually need to find the lowest common ancestor of two target nodes. Then, we can think the LCA to be root and the target nodes exist in two different branches. (Example 1)
Or there can be situation that both the target nodes exists on same root to leaf path that means one of the two target nodes itself is LCA. (Example 2)
However rest of our job is two find distance of respective target nodes from the LCA.
Let the distances to be distance1 and distance2 respectively.
Then the minimum distance between the two target nodes will be = distance1+distance2
How to find LCA?
Can be done using preorder traversal.
Pre-requisite:
Tree root, target node data values a, b
After finding the LCA we compute the distance separately for two nodes. This can be done by level order traversal finding number of levels between target node and root (LCA).
Example with explanation:
Example 1:
Example 2:
C++ implementation:
Output