fork download 
  1. import java.util.*;
  2. class Node{
  3.     int key;
  4.     Node lChild;
  5.     Node rChild;
  6.     Node(int key){
  7.          this.key=key;
  8.          this.lChild=null;
  9.          this.rChild=null;
  10.     }
  11. }
  12. class BSTree{
  13.     Node root;    
  14.     public Node insert(int key, Node root){
  15.         if(root==null){           
  16.             return new Node(key);
  17.         } else{           
  18.             if(key>root.key){
  19.                 root.rChild=insert(key,root.rChild);
  20.  
  21.             }
  22.             else{
  23.                 root.lChild=insert(key,root.lChild);
  24.  
  25.             }                
  26.         }
  27.         return root;
  28.     }
  29.     public void inOrderTraversal(Node root){
  30.         if(root==null)
  31.             return ;
  32.         inOrderTraversal(root.lChild);
  33.         System.out.print(root.key+" ");
  34.         inOrderTraversal(root.rChild);
  35.     }
  36. }
  37. class PrintAllNodeWhichAreKDistanceFromLeaf{
  38.     public static void main(String []args){
  39.         Scanner scan=new Scanner(System.in);
  40.         BSTree rootNode=new BSTree();
  41.         rootNode.root=null;
  42.         int size=scan.nextInt();// size of BSTree
  43.  
  44.         for(int i=0;i<size;i++){
  45.             int data=scan.nextInt();  // take root value          
  46.             rootNode.root=rootNode.insert(data,rootNode.root);// insert node in bst
  47.         }  
  48.         // K is the distance 
  49.         int K=scan.nextInt();
  50.         //rootNode.inOrderTraversal(rootNode.root); 
  51.         System.out.println("\nNodes which are at K distance");
  52.         printNodesAtKDistanceFromLeaf(rootNode.root,K,size);
  53.     }
  54.     public static void printNodesAtKDistanceFromLeaf(Node root, int K, int size){
  55.         int [] path=new int[size];
  56.         printNodesAtDistanceUtil(root,K,0,path);
  57.         return;
  58.     }
  59.     public static void printNodesAtDistanceUtil(Node root,int k, int len, int [] path){
  60.         if(root==null)
  61.             return;
  62.         path[len]=root.key;
  63.  
  64.         len++;
  65.         if(root.lChild==null && root.rChild==null  && len-k-1>=0){
  66.             System.out.print(path[len-k-1]+" ");
  67.             return;
  68.         }
  69.         printNodesAtDistanceUtil(root.lChild,k,len,path);
  70.         printNodesAtDistanceUtil(root.rChild,k,len,path);
  71.     }
  72. }
  73.  
Success #stdin #stdout 0.15s 321088KB
comments (?)
stdin 
12
10 5 6 7 3 4 17 20 15 16 18 19
2
stdout 
Nodes which are at K distance
5 5 17 20
https://ideone.com/ECoUOl
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!