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

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

__________________________________________________

### Like this:

Like Loading...

*Related*