Print nodes at k distance from root in binary tree (java/ recursive/ example)

• Given a binary tree, print nodes at k distance from root node using recursive algorithm.
  • K should have value <= height of a binary tree.
• Perform binary tree traversal using depth first search recursive (DFS) algorithm.
• We have already discussed similar problem Print paths from root to leaf nodes in binary tree .

Algorithm: print nodes at k = 3 distance from root node A in binary tree

• Print nodes at distance K = 3 from root node
• At node A, check whether current distance K is equal to 0 [K = 3]
  • 3 == 0 ?, No, Node A will not be printed.
  • Traverse left subtree (Node B) & pass K-1 for left subtree i.e. K=2
    • Check 2 == 0 ? , No,  Node B will not be printed.
    • Traverse left subtree (Node D) & K-1 for left subtree i.e. K=1
      • Check 1 == 0 ?, No, Node D will not be printed.
    • Traverse right subtree (Node E) and K-1 for right subtree i.e. K=1
      • Check 1 == 0 ? No, Node E will not be printed.
  • Traverse right subtree (Node C) and pass K-1 for right subtree i.e. K=2
    • Check 2 == 0 ? No, Node C will not be printed.
    • Traverse left subtree (Node F) and pass K-1 for left subtree i.e. K=1
      • Check 1 == 0 ?  Node F will not be printed.
      • Traverse left subtree (Node H) and pass K-1 for left subtree i.e. K=0
        • Check 0 == 0 ? Node H will be printed
      • Traverse right subtree (Node I) and pass K-1 for right subtree i.e. K=0
        • Check 0 == 0 ? Node I will be printed
    • Traverse right subtree (Node G) and pass K-1 for right subtree i.e. K=1
      • Node J & Node K will be printed

Nodes at K distance from root node in a binary tree:

Summarize algorithm – nodes at k distance from root node

• Check the K distance == 0 at every node (if its true print the node)
• Decrement the distance by 1, while passing to its subtree (left or right subtree)

Program – print nodes at k distance from root in binary tree using java

1.) PrintNodesKDistFromRoot Class:

• PrintNodesKDistFromRoot class print the nodes at K distance from Root node in a binary tree.
• Traverse the binary tree using depth first search recursive algorithm.

package org.learn.Question;

import org.learn.PrepareTree.Node;

public class PrintNodesKDistFromRoot {

	public static void printNodesKDistFromRoot(Node root, int distance) {
		if(null == root) {
			return;
		}
		
		if(distance == 0) {
			System.out.printf(" %d ",root.data);
		} else if(distance > 0) {		
			printNodesKDistFromRoot(root.left, distance - 1);
			printNodesKDistFromRoot(root.right, distance - 1);
		}
		return;
	}	
}

2.) Node Class:

• Node class representing the nodes of a binary tree.

package org.learn.PrepareTree;

public class Node {
	public int data;
	public Node left;
	public Node right;

	public Node(int num) {
		this.data = num;
		this.left = null;
		this.right = null;
	}

	public Node() {
		this.left = null;
		this.right = null;
	}
	public static Node createNode(int number) {
		return new Node(number);
	}
}

3.) App Class:

• We are creating the binary tree in main method
• We are calling PrintNodesKDistFromRoot class, to print the nodes at K distance from root node in a binary tree

package org.learn.Client;

import org.learn.PrepareTree.Node;
import org.learn.Question.PrintNodesKDistFromRoot;

public class App 
{
    public static void main( String[] args )
    {  
       //root level 0
       Node A = Node.createNode(100);
       //Level 1
       Node B = Node.createNode(50);
       Node C = Node.createNode(150);
       //Level 2
       Node D = Node.createNode(25);
       Node E = Node.createNode(75);
       Node F = Node.createNode(125);
       Node G = Node.createNode(175);
       //Level 3
       Node H = Node.createNode(120);
       Node I = Node.createNode(140);
       Node J = Node.createNode(160);
       Node K = Node.createNode(190);
             
       //connect Level 0 and 1
       A.left = B;
       A.right = C;
       //connect level 1 and level 2
       B.left = D;
       B.right = E;
       C.left = F;
       C.right = G;
       //Connect level 2 and level 3
       F.left = H;
       F.right = I;
       G.left = J;
       G.right = K;
       
       int distance = 1;
       System.out.printf("Nodes at distance %d from root \n",distance);
       PrintNodesKDistFromRoot.printNodesKDistFromRoot(A,distance);  
       
       distance = 2;
       System.out.printf("\nNodes at distance %d from root \n",distance);
       PrintNodesKDistFromRoot.printNodesKDistFromRoot(A,distance);     
       distance = 3;
       System.out.printf("\nNodes at distance %d from root \n",distance);
       PrintNodesKDistFromRoot.printNodesKDistFromRoot(A,distance);  
    }
}

Nodes at k distance from root in binary tree (java / recursive)

Nodes at distance 1 from root
50  150
Nodes at distance 2 from root
25  75  125  175
Nodes at distance 3 from root
120  140  160  190

Download code-Print nodes at K distance root node java recursive