Find The Distance From Root To Given Node of a Binary Tree.

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.

Distance from root to given node
Distance from root to given node

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