Print All The Nodes Which are X distance from the Leaf Nodes

by

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

Example :

Print All The Nodes Which are X distance from the Leaf Nodes
Print All The Nodes Which are X distance from the Leaf Nodes

Approach:

  • This Problem is the extension of ” Print paths from root to all leaf nodes“
  • Instead of printing all the nodes in array, print nodes which are at (pathLength-x), which will the nodes which are the x distance from the leaf nodes.
  • To avoid printing the redundant values, because one node can be at the x distance from the multiple leaf nodes, use boolean visited[] ( similar to path[] ) and mark it true once the node is printed.

Complete Code:

public class NodesAtKdistanceFromLeaf {
public void printPaths(Node root, int[] path, int pathLen,
boolean [] pathVisited, int distance) {
if (root == null) {
return;
}
path[pathLen] = root.data;
pathVisited[pathLen] = false;
pathLen++;
if (root.left == null && root.right == null) {
int nodeAtDistance = pathLen – distance – 1;
if (nodeAtDistance >= 0 && pathVisited[nodeAtDistance] == false) {
System.out.print(" " + path[nodeAtDistance]);
pathVisited[nodeAtDistance] = true;
}
} else {
printPaths(root.left, path, pathLen,pathVisited, distance);
printPaths(root.right, path, pathLen,pathVisited, distance);
}
}
public static void main(String[] arg) {
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(7);
root.right.left = new Node(6);
root.right.left.left = new Node(8);
root.right.left.right = new Node(9);
int[] path = new int[100];
boolean[] pathVisited = new boolean[100];
NodesAtKdistanceFromLeaf p = new NodesAtKdistanceFromLeaf();
System.out.print("Nodes at distance by 2 :");
p.printPaths(root, path, 0, pathVisited, 2);
System.out.print("\nNodes at distance by 1 :");
p.printPaths(root, path, 0, pathVisited, 1);
}
}
class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
left = null;
right = null;
}
}

view raw
NodesAtKdistanceFromLeaf.java
hosted with ❤ by GitHub


Output:

Nodes at distance by 2 :  2  3
Nodes at distance by 1 :  4  6

Related Posts: