# Find the Distance between Two Nodes of a Binary Tree.

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

### 1 thought on “Find the Distance between Two Nodes of a Binary Tree.”

1. 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) {