Menu
How do I find the distance between two nodes in a binary tree? Equivalently, what algorithms are there for finding the most recent common ancestor (lowest common ancestor) of two nodes?
223
The distance between two nodes can be obtained in terms of lowest common ancestor. Following is the formula. Dist(n1, n2) = Dist(root, n1) + Dist(root, n2) - 2*Dist(root, lca) 'n1' and 'n2' are the two given keys 'root' is root of given Binary Tree.
The distance between two nodes is defined as the total number of edges in the shortest path from one node to other. For example, consider the binary tree. The distance between node 7 and node 6 is 3. This problem is a standard application of the lowest common ancestor of given nodes.
153
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
