Objective: – Find The Distance From Root To Given Node of a binary tree.
What does Distance means : It means number of edges between two nodes.
Approach:
- This problem is similar to “Find Path From Root To Given Node“
- Make the following change into that
- Instead of returning the boolean value return the integer, nodes in the path will return the number = 1 + number returned by pervious node in path .
- The final return will give you the number of nodes between root and the given leaf node so the distance will be (edges)= number of nodes -1
Complete Code:
| public class DistanceRootToNode { | |
| 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) { | |
| return x + 1; | |
| } | |
| return 0; | |
| } | |
| return 0; | |
| } | |
| 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); | |
| DistanceRootToNode i = new DistanceRootToNode(); | |
| System.out.println("Distance from root to 45 is : " | |
| + (i.Pathlength(root, 45)–1)); | |
| } | |
| } | |
| class Node { | |
| int data; | |
| Node left; | |
| Node right; | |
| public Node(int data) { | |
| this.data = data; | |
| this.left = null; | |
| this.right = null; | |
| } | |
| } |
Output :
Distance from root to 45 is : 3