This post is completed by 1 user

  • 0
 Add to List
Hard

79. Calculate Distance Between Nodes in a Binary Tree

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

Example :

Distance-between-two-nodes-example

Approach:

  1. Distance(X, Y) = Distance(root, X) +Distance(root, Y) - 2*(Distance(root to LCA(X,Y)
  2. where LCA(X,Y) = Lowest Common Ancestor of X,Y
  3. In the above example if Distance(20,45) = 3
  4. Distance(root, 20) = 2
  5. Distance(root, 45) = 3
  6. LCA(20, 45) = 10
  7. Distance(root, 10) = 1
  8. Distance(20,45) = 2+3 - 2*1 = 3

Now the problem is reduced to How to find the distance from the root to any given node and How to find Lowest Common Ancestor of two given nodes.

 

Output:

Distance between 45 and 20 is : 3

Related Problems: