# Print nodes at K distance from Leaf node in Binary tree.

### Print nodes at K distance from Leaf in binary tree. ORPrint all nodes that are at distance k from a leaf node.

Given a Binary Tree, Print all Nodes that are at K distance from leaf node in Binary Tree. Lets understand what will be input and expected output with the help of an example.

If k = 1. It means we need to print all nodes that are at distance 1 from Leaf node.

In Case 2, we have 4 leaf nodes (Node 1, Node 10, Node 5, Node7).
Node at distance K that is Node at distance 1 from leaf Node 1 is Node 2 (Print 2)
Node at distance K that is Node at distance 1 from leaf Node 10 is Node 9 (Print 9)
Node at distance K that is Node at distance 1 from leaf Node 5 is Node 6 (Print 6)
Node at distance K that is Node at distance 1 from leaf Node 7 is Node 6 (6 already printed, ignore)

### Algorithm

We already saw how to Print Nodes at K distance from Root in Binary Tree

If you are not familar with Pre order traversal, I would suggest to have a look at Pre-order traversal first: Pre-Order Traversal of Binary Tree

In this post, we need to Print nodes that are at K distance from Leaf nodes in Binary Tree.

STEP 1: Traverse the Tree in Pre-order traversal and increment variable currentDistanceFromRoot
which captures distance of node from Root node.

STEP 2: Also, while traversing a tree, we will capture all the nodes in a Path until we encounter a
Leaf node. This will help us to identify Node at distance K from Leaf node.

STEP 3: When we reach a Leaf node that is a node which doesn't has left and right child, we need to
find a node which is at K distance away from current Leaf  node.
(currentDistanceFromRoot - K) will give us index of Node which is at K distance away
from current Leaf node.
We will directly look into Path and print Node present at that index.

Remember, we need to print Node which is at K distance away from Leaf node only once,

In above image, when K=2, that is we need to find node that are at distance 2 from leaf node.
From leaf Node 10, Node which is present at distance 2 is Node 2.
From leaf Node 20, Node which is present at distance 2 is Node 2.

So we need to avoid printing Node 2 twice and for this, we need to maintain a flag, which mark which nodes are already printed.

### Java Program to Print Nodes at K distance from Leaf Node.

```package tree;

public class PrintNodesAtKDistanceFromLeaf {

public static void main(String[] args) {
new PrintNodesAtKDistanceFromLeaf();
}

public PrintNodesAtKDistanceFromLeaf(){

Node rootNode=null;
rootNode  = addNode(rootNode, 50);
rootNode  = addNode(rootNode, 60);
rootNode  = addNode(rootNode, 70);
rootNode  = addNode(rootNode, 80);
rootNode  = addNode(rootNode, 90);
rootNode  = addNode(rootNode, 69);
rootNode  = addNode(rootNode, 68);
rootNode  = addNode(rootNode, 67);

printNodesAtDistanceKFromLeafHelper(rootNode, 4);
}

public static void printNodesAtDistanceKFromLeafHelper(Node root,int k){
if(root==null){
return;
}
List<Integer> pathList= new ArrayList<Integer>();
List<Boolean> alreadyVisitedFlagList= new ArrayList<Boolean>();

printNodesAtDistanceKFromLeaf(root, k, 0, pathList, alreadyVisitedFlagList);
}

//prints all the keys which are K distant from a leaf
public static void printNodesAtDistanceKFromLeaf(Node root,int k, int currentDistanceFromRoot, List<Integer> pathList, List<Boolean> alreadyVisitedFlagList){
if(root==null){
return;
}

//Add entry in Path and mark as node not yet printed.

//reach leaf node if condition is true.
if(root.getLeft()==null && root.getRight()==null){

//we reach leaf node, So get the index of node that is K distance away from this leaf node.
int indexToPrint = currentDistanceFromRoot - k;

//If index is <0, it means user give invalid K value and K distance doesn't exist.
//If index is >=0, it means K distance exist and check whether we already printed that node.
if(indexToPrint >=0 && !alreadyVisitedFlagList.get(indexToPrint)){

System.out.print(pathList.get(indexToPrint) + " ");

//marking as node already printed.
return;
}
}

if(root.getLeft()!=null){
printNodesAtDistanceKFromLeaf(root.getLeft(), k, currentDistanceFromRoot+1, pathList, alreadyVisitedFlagList);

// Already visited Left subtree of current node. Remove current node form pathList
pathList.remove(currentDistanceFromRoot+1);

// Already visited Left subtree of current node. Remove current node form alreadyVisitedFlagList
}

if(root.getRight()!=null){
printNodesAtDistanceKFromLeaf(root.getRight(), k, currentDistanceFromRoot+1, pathList, alreadyVisitedFlagList);

// Already visited Right subtree of current node. Remove current node form pathList.
pathList.remove(currentDistanceFromRoot+1);

// Already visited Right subtree of current node. Remove current node form alreadyVisitedFlagList
}
}

private Node addNode(Node rootNode, int i) {
if(rootNode==null){
return new Node(i);
}else{
if(i > rootNode.getData()){

}else{
}
}
return rootNode;
}
}

```
Other Solution:
```public static Set<Integer> kDistantFromLeafAnotherApproach(Node root,int k){
if(root==null){
Set<Integer> s = new HashSet<Integer>();
return s;
}

Set<Integer> s = new HashSet<Integer>();

Set<Integer> left = kDistantFromLeafAnotherApproach(root.getLeft(), k);
Set<Integer> right = kDistantFromLeafAnotherApproach(root.getRight(), k);

if(root.getLeft()==null){
left = right;
}
if(root.getRight()==null){
right = left;
}

Set<Integer> temp = new HashSet<Integer>();

for (Integer i : s) {
if((i+1)==k){
System.out.print(root.getData() + " ");
break;
}else{
}
}
return temp;
}

```

### You may also like to see

#### Advanced Multithreading Interview Questions In Java

Enjoy !!!!

If you find any issue in post or face any error while implementing, Please comment.