Find the Distance between Two Nodes of a Binary Tree.

by · December 8, 2014

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

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) = 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:


Output:

Distance between 45 and 20 is : 3

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

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

Tags:

  • Pramod Vidyagar

    Hi,
    Thanks for the program., its cool ..
    There is 1 thing I would like to suggest is to have a better readable piece of code to get the node count ..

    You should get -1 for the node which is not in the tree.
    private static int findNodeCount(Node head, int n, int count) {
    if(head == null ){
    return -1;
    }
    if(head.data == n){
    return count;
    }
    int leftCount = findNodeCount(head.left, n, count+1);
    return leftCount > -1 ? leftCount : findNodeCount(head.right, n, count+1);
    }

Follow:

Select level

Beginner
Intermediate
Expert

Follow me on Twitter

%d bloggers like this: