Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Find the Distance between Two Nodes of a Binary Tree.

Objec­tive: - Given nodes in a binary tree, find the dis­tance between them.

Exam­ple :

Distance-between-two-nodes-example

Distance-between-two-nodes-example

Approach:

  • Distance(X, Y) = Distance(root, X) +Distance(root, Y) — 2*(Distance(root to LCA(X,Y)
  • where LCA(X,Y) = Low­est Com­mon Ances­tor of X,Y
  • In the above exam­ple 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 prob­lem is reduced to How to find dis­tance from root to any given node and How to find Low­est Com­mon Ances­tor of two given nodes.

Com­plete Code:


Out­put:

Distance between 45 and 20 is : 3

You may also like...