This post is completed by 1 user
|Add to List|
Find the Distance between Two Nodes of a Binary Tree.
Objective: - Given nodes in a binary tree, find the distance between them.
- Distance(X, Y) = Distance(root, X) +Distance(root, Y) - 2*(Distance(root to LCA(X,Y)
- where LCA(X,Y) = Lowest Common Ancestor of X,Y
- In the above example if Distance(20,45) = 3
- Distance(root, 20) = 2
- Distance(root, 45) = 3
- LCA(20, 45) = 10
- Distance(root, 10) = 1
- Distance(20,45) = 2+3 - 2*1 = 3
Now the problem is reduced to How to find distance from root to any given node and How to find Lowest Common Ancestor of two given nodes.
Distance between 45 and 20 is : 3