###
Print nodes at K distance from Leaf in binary tree. OR

Print 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.

**(currentDistanceF**

**romRoot - 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. pathList.add(root.getData()); alreadyVisitedFlagList.add(false); //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. alreadyVisitedFlagList.set(indexToPrint, true); 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 alreadyVisitedFlagList.remove(currentDistanceFromRoot+1); } 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 alreadyVisitedFlagList.remove(currentDistanceFromRoot+1); } } private Node addNode(Node rootNode, int i) { if(rootNode==null){ return new Node(i); }else{ if(i > rootNode.getData()){ Node nodeToAdd = addNode(rootNode.getRight(), i); rootNode.setRight(nodeToAdd); }else{ Node nodeToAdd = addNode(rootNode.getLeft(), i); rootNode.setLeft(nodeToAdd); } } return rootNode; } }

**Other Solution:**public static Set<Integer> kDistantFromLeafAnotherApproach(Node root,int k){ if(root==null){ Set<Integer> s = new HashSet<Integer>(); s.add(-1); 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; } s.addAll(left); s.addAll(right); Set<Integer> temp = new HashSet<Integer>(); for (Integer i : s) { if((i+1)==k){ System.out.print(root.getData() + " "); break; }else{ temp.add(i+1); } } return temp; }

### You may also like to see

#### Compress a given string in-place and with constant extra space.

#### Check whether a given string is an interleaving of String 1 and String 2.

#### Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord.

#### Serialize and Deserialize a Binary Tree

#### Advanced Multithreading Interview Questions In Java

**Enjoy !!!!**

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

## Post a Comment