fork download
copy 
  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.         boolean [] visitedNode=new boolean[size];
  57.         Arrays.fill(visitedNode, false);
  58.         printNodesAtDistanceUtil(root,K,0,path,visitedNode);
  59.         return;
  60.     }
  61.     public static void printNodesAtDistanceUtil(Node root,int k, int len, int [] path, boolean[] visitedNode){
  62.         if(root==null)
  63.             return;
  64.         path[len]=root.key;
  65.         visitedNode[len]=false;
  66.         len++;
  67.         if(root.lChild==null && root.rChild==null && visitedNode[len-k-1]==false && len-k-1>=0){
  68.             System.out.print(path[len-k-1]+" ");
  69.             visitedNode[len-k-1]=true;
  70.             return;
  71.         }
  72.         printNodesAtDistanceUtil(root.lChild,k,len,path, visitedNode);
  73.         printNodesAtDistanceUtil(root.rChild,k,len,path, visitedNode);
  74.     }
  75. }
  76.  
Success #stdin #stdout 0.15s 321088KB
comments (?)
stdin
copy 
12
10 5 6 7 3 4 17 20 15 16 18 19
2
stdout
copy 
5 17 20
https://ideone.com/PNelwg
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!