K distance from root

//K distance from root

import java.util.LinkedList; 
import java.util.Queue; 
import java.io.*;
import java.util.*;

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

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

class GfG {
    
    static Node buildTree(String str) {
        if(str.length() == 0 || str.charAt(0) == 'N') {
            return null;
        }
        
        String ip[] = str.split(" ");
        Node root = new Node(Integer.parseInt(ip[0]));
        Queue<Node> queue = new LinkedList<>(); 
        queue.add(root);
        int i = 1;

        while(queue.size() > 0 && i < ip.length) {
            Node currNode = queue.peek();
            queue.remove();
            String currVal = ip[i];

            if(!currVal.equals("N")) {
                currNode.left = new Node(Integer.parseInt(currVal));
                queue.add(currNode.left);
            }
            i++;

            if(i >= ip.length)
                break;
                
            currVal = ip[i];

            if(!currVal.equals("N")) {
                currNode.right = new Node(Integer.parseInt(currVal));
                queue.add(currNode.right);
            }
            i++;
        }
        
        return root;
    }
    
	public static void main (String[] args) throws IOException{
	        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	        int t=Integer.parseInt(br.readLine());
    
	        while(t > 0){
	          String X[] = br.readLine().trim().split(" ");
	          int k = Integer.parseInt(X[0]);
	          String s = br.readLine();
    	      Node root = buildTree(s);
        	  Tree g = new Tree();
			      ArrayList<Integer> nodes = g.Kdistance(root,k);

			      for(int i = 0; i < nodes.size(); i++) {
			        System.out.print(nodes.get(i)+ " ");
			      }
			      System.out.println();
            t--;       
          }
    } 
}

class Node {
   int data;
   Node left, right;
   
   Node(int item) {
        data = item;
        left = right = null;
    }
}

class Tree {
    ArrayList<Integer> nodes = new ArrayList<>();
        
    ArrayList<Integer> Kdistance(Node root, int k) {
        nodes = new ArrayList<>();
        dfs(root, k);
        
        return nodes;
    }
    
    void dfs(Node root, int k){
        if(root == null) {
            return;
        }
        
        if(k == 0) {
            nodes.add(root.data);
        }
        
        else {
            dfs(root.left, k-1);
            dfs(root.right, k-1);
        }
     }
}