Be the first user to complete this post
|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
Distance between 45 and 20 is : 3
- Populate Next Siblings Pointers in a Given Binary Tree OR Populate Next Right Pointers in Each Node Hard