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

**Code:**

**Output:**

Distance between 45 and 20 is : 3

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);

}