Print All The Nodes Which are X distance from the Given Node

Objective: Given Binary Tree, Print All The Nodes Which are X distance from the Given Node.

Example :

Approach:

Quite Tricky solution, i will explain using the example given in the picture.
Find out all the nodes which are at distance ‘3’ from the given node 5.

  1. Find the height of the given node 5 is -3. say x = 3.
  2. For all the nodes which are at distance 3 and exist below node 5, consider 5 as root node and problem will reduce to “Print all the nodes which are at distance x from the root”. Agree?.
  3. But what about the other nodes, go one level up ( at the path from root to node 5), which is node 2. since you have gone up by one level, x will be x = x-1 = 3-1 = 2.
  4. So now consider node 2 as root and again problem will reduce to, Print all the nodes which are at distance 2 from the root. remember one thing when considering the node 2 as root, you dont check the direction of node 5 .(Why,?? because if you check nodes at distance 2 from node 2, you will get 9, 7. Node 9 is at distance 3 from Node 5 which is right but Node 7 is at distance 1 from Node 5 which is wrong.)
  5. How would you stop your program to check in the direction of Node 5, when you go one level up, means at Node 2, after processing the Node 5, return Node 5 to Node 2 and at Node 2 check whether Node 5 is right child or left child of Node 2, based on that don’t check that direction.
  6. Now recursivley go one more level up, now x = x-1 = 2-1 =1. It will be Node 1, consider Node 1 as root and again problem will reduce to, Print all the nodes which are at distance 1 from the root and don’t check the direction of Node 2, with the same logic explained earlier.Print-All-The-Nodes-Which-are-X-distance-from-the-Given-Node-Implementation.1

Complete Code:

public class PrintAllNodesAtKFromGivenNode {
public void printAllNodes(Node root, int node, int distance) {
int pl = Pathlength(root, node) 1;
Path(root, node, pl, distance);
}
public void print(Node root, int node, Node prev, int k,
boolean searchingDown) {
if (root != null) {
if (k == 0 && root.data != node) {
System.out.print(" " + root.data);
}
if (searchingDown) {
print(root.left, node, prev, k, searchingDown);
print(root.right, node, prev, k, searchingDown);
} else {
if (root.left != prev) {
print(root.left, node, prev, k, searchingDown);
}
if (root.right != prev) {
print(root.right, node, prev, k, searchingDown);
}
}
}
}
public Node Path(Node root, int dest, int k, int n) {
if (root == null)
return null;
Node x = null;
if (root.data == dest || (x = Path(root.left, dest, k 1, n)) != null
|| (x = Path(root.right, dest, k 1, n)) != null) {
if (k == 0) {
print(root, dest, x, n k, true);
} else {
print(root, dest, x, n k, false);
}
return root;
}
return null;
}
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(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.left.left = new Node(9);
root.left.right = new Node(5);
root.left.right.left = new Node(6);
root.left.right.right = new Node(7);
root.left.right.right.right = new Node(10);
root.left.right.right.right.left = new Node(11);
root.right.right = new Node(8);
PrintAllNodesAtKFromGivenNode i = new PrintAllNodesAtKFromGivenNode();
System.out.print("Nodes at distance '3' from Node '5' are : ");
i.printAllNodes(root, 5, 3);
}
}
class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}


Output:

Nodes at distance '3' from Node '5' are : 11 9 3

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.