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

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

Example :

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;
	}
	}

Output:

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