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 .

K distance root node binary tree — Fig 1: Nodes at K distance (root node)

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 K Distance root leaf depth first search recursive algorithm — Fig 2: Nodes at K distance from root node

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

Distance	Nodes
0	A
1	B, C
2	D, E, F, G
3	H, I, J, K

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

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

Summarize algorithm – nodes at k distance from root node

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

1.) PrintNodesKDistFromRoot Class:

2.) Node Class:

3.) App Class:

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

You may also like: