Minimum Distance between 2 given Nodes of a Binary Tree

This logic is largely based on LCA of Binary Tree

So, we can understand from the statement that:

The min distance would be the distance from the root to one node + the dist between the root to the other node. This root may not be the main root of the tree, but will be some node that we will encounter while traversing the tree.

So, we need to see if a subtree contains the target node or not. We can use the Lowest Common Ancestor approach of writing code here.

Basically, it is a bottom up recursive logic. We need to return something based on conditions, and it will be like transmitting a message. The message we will transmit is : If we have found neither, 1, or both targets in the subtrees.

If we have found neither, then we must return nothing.

If we have found both in one of the subtrees ( the other one will be returning nothing ), so we must transmit that information.

Otherwise, we have found something in both subtree. This must also mean it is the first time this is happening. ( Because, say it is not the first time, that means this root will be getting a message either from the left/or right subtree, where both has already been found)

So, if we are getting targets from both, then return this root. This is the LCA.

The distance will be( dist between this LCA and left target) + (dist between LCA and right target) . This should be stored somewhere, and that’s it.

Function f finds the LCA. Then again we traverse, store the distances (between LCA and each target) and add them.