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