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

  • Pramod Vidya­gar

    Hi,
    Thanks for the pro­gram., its cool ..
    There is 1 thing I would like to sug­gest is to have a bet­ter read­able piece of code to get the node count ..

    You should get –1 for the node which is not in the tree.
    pri­vate sta­tic int findNodeCount(Node head, int n, int count) {
    if(head == null ){
    return –1;
    }
    if(head.data == n){
    return count;
    }
    int left­Count = findNodeCount(head.left, n, count+1);
    return left­Count > –1 ? left­Count : findNodeCount(head.right, n, count+1);
    }