In Binary Search Tree,finding the distance between the nodes is easy.Travel up to the node where you need not take different paths.That node is called common ancestor node.From there calculate the distance of node1 as l1 and distance of node2 as l2.The distance between them is l1+l2.
In Binary Tree :
1)calculate the length from root to node1 as l1
2)calculate the length from root to node2 as l2
3)find the least common ancestor and calculate the distance up to that ancestor as l3.
4)resultant distance between the two nodes is l1+l2-2l3 (since we count the distance from root to least common ancestor twice)
In Binary Tree :
1)calculate the length from root to node1 as l1
2)calculate the length from root to node2 as l2
3)find the least common ancestor and calculate the distance up to that ancestor as l3.
4)resultant distance between the two nodes is l1+l2-2l3 (since we count the distance from root to least common ancestor twice)
No comments:
Post a Comment