fork download
copy 
  1. class BST {
  2.  private static Node root;
  3.  
  4.  public static void main(String [] args) {
  5.   int [] A = {8, 3, 10, 1, 6, 14, 4, 7, 13};
  6.   root = buildBST(root, A);
  7.   System.out.println("inorder: ");
  8.   printBSTInorder(root);
  9.   System.out.println();
  10.   int sizeBST = sizeOfBST(root);
  11.   System.out.println("Size of BST: " + sizeBST);
  12.  
  13.   for (int i=1; i<=sizeBST; i++) {
  14.    Node node = nthLargestNode(root, i);
  15.    System.out.println(i + " largest node: " + node.data);
  16.   }
  17.  }
  18.  
  19.  public static Node nthLargestNode(Node node, int N) {
  20.    if (null == node) 
  21.   {
  22.    return null;
  23.   }
  24.  
  25.   int R = sizeOfBST(node.right) + 1;
  26.   if (N == R) 
  27.   {
  28.    return node;
  29.   }
  30.   if(N < R) 
  31.   {
  32.    return nthLargestNode(node.right, N);
  33.   } 
  34.   else 
  35.   {
  36.    return nthLargestNode(node.right, N-R);
  37.   }
  38.   }
  39.  
  40.  
  41.  public static int sizeOfBST(Node node) {
  42.   if (null == node) { return 0; }
  43.   return (sizeOfBST(node.left) + 1 + sizeOfBST(node.right));
  44.  }
  45.  
  46.  public static Node buildBST(Node node, int [] A) {
  47.   if (A == null) { return null; }
  48.   int len = A.length;
  49.   for (int i=0; i<len; i++) {
  50.    node = insertIntoBST(node, A[i]);
  51.   }
  52.   return node;
  53.  }
  54.  
  55.  private static Node insertIntoBST(Node node, int value) {
  56.   if (null == node) {
  57.    return new Node(value);
  58.   }
  59.   if (value <= node.data) {
  60.    node.left = insertIntoBST(node.left, value);
  61.   } else {
  62.    node.right = insertIntoBST(node.right, value);
  63.   }
  64.   return node;
  65.  }
  66.  
  67.  public static void printBSTInorder(Node node) {
  68.   if (null == node) {  return ; }
  69.   if (null != node.left) {
  70.    printBSTInorder(node.left);
  71.   }
  72.   System.out.print(node.data + " ");
  73.   if (null != node.right) {
  74.    printBSTInorder(node.right);
  75.   }
  76.  }
  77. }
  78.  
  79. class Node {
  80.  Integer data;
  81.  Node left;
  82.  Node right;
  83.  
  84.  public Node(Integer data) {
  85.   this.data = data;
  86.   this.left = null;
  87.   this.right = null;
  88.  }
  89. }
Runtime error #stdin #stdout 0.03s 245632KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
inorder: 
1 3 4 6 7 8 10 13 14 
Size of BST: 9
1 largest node: 14
https://ideone.com/rUQbn
language:
Java (HotSpot 12)
created:
12 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!