Dinesh on Java

In this article, we will discuss how to print nodes at k distance from the root of a binary tree. The trees are hierarchical data structures unlike Arrays, Linked Lists, Stack and queues, which are linear data structures. In the tree, the topmost node is known as the root of the tree. Other elements that are directly under an element are called its children. The element directly above something is called its parent. Let’s see the following diagram of the binary tree data structure:

 tree
      ----
       j    <-- root
     /   \
    f      k  
  /   \      \
 a     h      z    <-- leaves

Let’s see the tree node representation in Java code like the following:

/**
 * Class containing left and right child of current node and key value
 */
package com.dineshonjava.algo;

/**
 * @author Dinesh.Rajput
 *
 */
public class TreeNode {
	
	int data;
	TreeNode left, right;
    TreeNode(int item)
    {
        data = item;
        left = right = null;
    }
}

In previous articles we have discussed some important algorithm related to the linked list like the following:

• Find the nth node from the end of a singly linked list
• Find the middle element in a linked list
• How to Reverse linked list in Java
• Delete given node from a singly linked list

Let’s discuss the algorithm to print nodes at k distance from the root of the binary tree.

Print nodes at k distance from the root

Given a root of a tree, and an integer k. Print all the nodes which are at k distance from the root. Let’s see the following code:

/**
 * 
 */
package com.dineshonjava.algo;

/**
 * @author Dinesh.Rajput
 *
 */
public class TreeTest {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		TreeNode root = new TreeNode(0); 
        
        root.left = new TreeNode(1); 
        root.right = new TreeNode(2); 
        
        root.left.left = new TreeNode(3); 
        root.left.right = new TreeNode(4); 
        root.right.left = new TreeNode(5); 
        root.right.right = new TreeNode(6);
        
        root.left.left.left = new TreeNode(7); 
        root.left.left.right = new TreeNode(8); 
        root.left.right.left = new TreeNode(9); 
        root.left.right.right = new TreeNode(10);
        
        root.right.left.left = new TreeNode(11); 
        root.right.left.right = new TreeNode(12); 
        root.right.right.left = new TreeNode(13); 
        root.right.right.right = new TreeNode(14);
        
        System.out.println("Nodes at 3 distance from the root");
        printKDistant(root, 3); 
	}

	private static void printKDistant(TreeNode node, int k) {
		if (node == null) 
            return; 
        if (k == 0)  
        { 	
            System.out.print(node.data + " "); 
            return; 
        }  
        else 
        { 
            printKDistant(node.left, k - 1); 
            printKDistant(node.right, k - 1); 
        } 
	}

}

Run above program, you will get the following output:

Nodes at 3 distance from the root
7 8 9 10 11 12 13 14 

As you can see the above output, we have printed all nodes with distance 3.

Hope, you have understood this solution for the above to print nodes at k distance from the root. Please share other solutions if you have. :).

Happy learning with us!!!.