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

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. 
                (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 javabypatel.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

---

Top Binary tree interview questions in Java

Find Kth SMALLEST element in BST(Binary Search Tree)

Check whether Binary Tree is foldable or not.

Check if two nodes are cousins in a Binary Tree.

Get Level/Height of node in binary tree

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

Construct a Binary Tree from In-order and Post-order traversals.

Print Nodes in Top View of Binary Tree.

Zig Zag Traversal of Binary Tree.

Enjoy !!!! 

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