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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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
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) {
if(head == null ){
return -1;
}
if(head.data == n){
return count;
}
int leftCount = findNodeCount(head.left, n, count+1);
return leftCount > -1 ? leftCount : findNodeCount(head.right, n, count+1);
}