Print nodes K distance from leaf node in binary tree ( java /DFS / example)

Given a binary tree, print nodes at k distance from leaf nodes using recursion.
- K should have value <= height of a binary tree.
Perform preOrder traversal in a binary tree using depth first search recursive (DFS) algorithm.
The logical flow of current problem is quite similar to Print paths from root to leaf nodes in binary tree .

K distance nodes binary tre — Fig 1: Nodes at K distance (leaf node)

Algorithm: print nodes at k distance from leaf nodes using java

Print a nodes at distance K = 2 from leaf nodes.
Perform pre order traversal
Add current node to array and mark current node un-visited [Node A]
If current node is not a leaf node
- Traverse the left sub tree [Node B]
  - Add Node B to array and mark it un-visited
  - Traverse the left sub tree [Node D]
    - Add Node D to array and mark it un-visited
      - Node D is leaf node and its not visited earlier.
        
        Print Node at K distance from array
        
        Print Node A (100) & mark Node A as visited.
    - Traverse the right sub tree [Node E]
      - Add Node E to array and mark it un-visited
      - Node E is leaf node and its not visited earlier.
        
        Already visited node at K = 2 [Node A]
        
        Node A would not be printed
- Traverse the right sub tree [Node C]
  - Add Node C to array and mark it un-visited
  - Follow the algorithm same (left sub-tree) & Node C will be printed
Similarly, print nodes in all sub-trees. (ref Fig 2)

binary tree distance leaf node — Fig 2: Nodes at K distance from leaf nodes

We have summarized nodes at K distance from leaf nodes as follows:

K(Distance)	Output
1	B,F,G
2	A,C
3	A

Summary of above algorithm is as follows:

Save the node data in array
Mark the current node as unvisited node (false)
Traverse the binary tree till, we encounter the leaf node
- If we have not visited the node earlier, let us print it and mark it visited
Follow the same procedure for all nodes

Program: print nodes K distance from leaf node in binary tree (java)

1.) PrintNodesKDistFromLeaf Class:

Traverse the binary tree using depth first search recursive algorithm.
Print the nodes at K distance from a leaf nodes in a binary tree.

package org.learn.Question;
 
import org.learn.PrepareTree.Node;
 
public class PrintNodesKDistFromLeaf {
 
    private static void printNodes(Node root, int distance,int index, int[] data, 
                                                            boolean[] isVisitedBefore) {
        if(null == root) {
            return;
        }       
        data[index] = root.data;
        isVisitedBefore[index] = false;     
        if(root.left == null && root.right == null &&
                index - distance  >= 0 && isVisitedBefore[index-distance] == false) {
            System.out.printf(" %d ",data[index-distance ]);
            isVisitedBefore[index-distance] = true;
        } else if(distance > 0) {    
            index++;
            printNodes(root.left, distance,index, data, isVisitedBefore);
            printNodes(root.right, distance,index, data, isVisitedBefore);
        }
        return;
    }   
     
    public static void printNodesKDistFromLeaf(Node root, int distance) {
        int data[]= new int[1024];
        boolean visit[]= new boolean[1024];
        printNodes(root, distance, 0, data, visit);
    }
}

2.) Node Class:

Node class represents 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 PrintNodesKDistFromLeaf class, to print nodes at K distance from a leaf nodes.
We are traversing the binary tree using depth first search algorithm.

package org.learn.Client;
 
import org.learn.PrepareTree.Node;
import org.learn.Question.PrintNodesKDistFromLeaf;
 
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 Leaf Node \n",distance);
       PrintNodesKDistFromLeaf.printNodesKDistFromLeaf(A,distance);  
        
       distance = 2;
       System.out.printf("\nNodes at distance %d from Leaf Node\n",distance);
       PrintNodesKDistFromLeaf.printNodesKDistFromLeaf(A,distance);     
       distance = 3;
       System.out.printf("\nNodes at distance %d from Leaf Node\n",distance);
       PrintNodesKDistFromLeaf.printNodesKDistFromLeaf(A,distance);  
    }
}

Output: print nodes K distance from leaf node in binary tree (java)

Nodes at distance 1 from Leaf Node
50 125 175
Nodes at distance 2 from Leaf Node
100 150
Nodes at distance 3 from Leaf Node
100

Print nodes K distance from leaf nodes in a binary tree ( java/DFS /example)

Algorithm: print nodes at k distance from leaf nodes using java

Program: print nodes K distance from leaf node in binary tree (java)

1.) PrintNodesKDistFromLeaf Class:

2.) Node Class:

3.) App Class:

Output: print nodes K distance from leaf node in binary tree (java)

Download code – print nodes K Distance from leaf (DFS)

Algorithm: print nodes at k distance from leaf nodes using java

Program: print nodes K distance from leaf node in binary tree (java)

1.) PrintNodesKDistFromLeaf Class:

2.) Node Class:

3.) App Class:

Output: print nodes K distance from leaf node in binary tree (java)

You may also like: