Objective: – Given nodes in a binary tree, find the distance between them.

Example :

Approach :

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 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 .

Complete Code: Run This Code

Run This Code
Output :

Distance between 45 and 20 is : 3
__________________________________________________
Top Companies Interview Questions..-

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

Like this: Like Loading...