/***
You are given 2 pointers to two nodes (p1, p2) in a binary tree. Devise an algorithm to find the distance between p1 and p2 (i.e. the length of the shortest path between them).
***/
Trace back to the top of the tree from each node, recording the left and right subtrees as 0 and 1 in a binary string. Compare the binary strings. The sum of the lengths of the two minus twice the length of the common parts at the end gives the distance.
3 comments:
in a Binary , you will not have a dual path from one node to other .
Correct if i am wrong ..
Thanks
Achuth R
your question is not clear to me.
In A binary tree each node will have one parent and atmost two children. Now the solution says when you traverse up the tree u will get the binary string mentioned. Now compare this binary string with the binary string obtained for the other node. Take the common path length and then sub from the twice the sum to get the distance. Hope its clear now.
Awesome
Post a Comment