fork download
  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
stdin
Standard input is empty
stdout
inorder: 
1 3 4 6 7 8 10 13 14 
Size of BST: 9
1 largest node: 14