Print nodes K distance from leaf nodes in a 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 .

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)

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

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

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