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.

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