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