Find distance between two nodes in a binary tree

Exam­ple :

Dis­tance between two nodes example

Appraoch:

• Distance(X, Y) = Distance(root, X) +Distance(root, Y) — 2*(Distance(root to LCA(X,Y)
• where LCA(X,Y) = Low­est Com­mon Ances­tor of X,Y
• In the above exam­ple 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 prob­lem is reduced to How to find dis­tance from root to any given node and How to find Low­est Com­mon Ances­tor of two given nodes.

Com­plete Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68

package PrintDistanceBwTwoNodes;     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