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

public class PrintDistance { | |

public int findDistance(Node root, int n1, int n2) { | |

int x = Pathlength(root, n1) – 1; | |

int y = Pathlength(root, n2) – 1; | |

int lcaData = findLCA(root, n1, n2).data; | |

int lcaDistance = Pathlength(root, lcaData) – 1; | |

return (x + y) – 2 * lcaDistance; | |

} | |

public int Pathlength(Node root, int n1) { | |

if (root != null) { | |

int x = 0; | |

if ((root.data == n1) || (x = Pathlength(root.left, n1)) > 0 | |

|| (x = Pathlength(root.right, n1)) > 0) { | |

// System.out.println(root.data); | |

return x + 1; | |

} | |

return 0; | |

} | |

return 0; | |

} | |

public Node findLCA(Node root, int n1, int n2) { | |

if (root != null) { | |

if (root.data == n1 || root.data == n2) { | |

return root; | |

} | |

Node left = findLCA(root.left, n1, n2); | |

Node right = findLCA(root.right, n1, n2); | |

if (left != null && right != null) { | |

return root; | |

} | |

if (left != null) { | |

return left; | |

} | |

if (right != null) { | |

return right; | |

} | |

} | |

return null; | |

} | |

public static void main(String[] args) throws java.lang.Exception { | |

Node root = new Node(5); | |

root.left = new Node(10); | |

root.right = new Node(15); | |

root.left.left = new Node(20); | |

root.left.right = new Node(25); | |

root.right.left = new Node(30); | |

root.right.right = new Node(35); | |

root.left.right.right = new Node(45); | |

PrintDistance i = new PrintDistance(); | |

System.out.println("Distance between 45 and 20 is : " | |

+ i.findDistance(root, 45, 20)); | |

} | |

} | |

class Node { | |

int data; | |

Node left; | |

Node right; | |

public Node(int data) { | |

this.data = data; | |

this.left = null; | |

this.right = null; | |

} | |

} |

**Output**:

Distance between 45 and 20 is : 3