Print Nodes at K distance from Root in Binary Tree

Print nodes at K distance from root in binary tree. OR
Print nodes at Level K.


Given a Binary Tree, Print all Nodes that are at K distance from root node in Binary Tree. We can also think of this question as Print all nodes that belong to Level K.
 
Lets understand what will be input and expected output with the help of an example.
 

If k = 2. It means we need to print all nodes that are at distance 2 from Root node.
It also means we need to print all nodes at Level 2, because all Nodes of Level 2 will be at same distance from Root Node.

Algorithm


It is very easy and just require Pre-order traversal of 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

  1. Do a Pre-Order traversal of Tree and and decrement K each time you move to left or right.
  2. When K = 0, it means that is the level we are interested in.
    So print the Node and return.

Note:  Once we reach k = 0, no need to further explore the tree down, because we already reached the level that we are interested in, So going ahead is of no use.



Java Program to Print Nodes at K distance from Root.


public class PrintNodesAtKDistanceFromRoot {

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

	public PrintNodesAtKDistanceFromRoot(){

		Node rootNode=null;	
		rootNode  = addNode(rootNode, 50);
		rootNode  = addNode(rootNode, 30);
		rootNode  = addNode(rootNode, 70);
		rootNode  = addNode(rootNode, 20);
		rootNode  = addNode(rootNode, 40);
		rootNode  = addNode(rootNode, 10);
		rootNode  = addNode(rootNode, 25);
		rootNode  = addNode(rootNode, 60);
		rootNode  = addNode(rootNode, 80);
		

		printNodesAtLevel(rootNode, 0);
	}

	private void printNodesAtLevel(Node rootNode, int level) {
		if(rootNode==null){
			return;
		}
		
		if(level == 0){
			System.out.print(rootNode.getData() + " ");
			return;
		}
		
		printNodesAtLevel(rootNode.getLeft(), level - 1);
		printNodesAtLevel(rootNode.getRight(), level - 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;
	}
}



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