class BST {
private static Node root;
public static void main
(String [] args
) { int [] A = {8, 3, 10, 1, 6, 14, 4, 7, 13};
root = buildBST(root, A);
System.
out.
println("inorder: "); printBSTInorder(root);
int sizeBST = sizeOfBST(root);
System.
out.
println("Size of BST: " + sizeBST
);
for (int i=1; i<=sizeBST; i++) {
Node node = nthLargestNode(root, i);
System.
out.
println(i
+ " largest node: " + node.
data); }
}
public static Node nthLargestNode(Node node, int N) {
if (null == node)
{
return null;
}
int R = sizeOfBST(node.right) + 1;
if (N == R)
{
return node;
}
if(N < R)
{
return nthLargestNode(node.right, N);
}
else
{
return nthLargestNode(node.right, N-R);
}
}
public static int sizeOfBST(Node node) {
if (null == node) { return 0; }
return (sizeOfBST(node.left) + 1 + sizeOfBST(node.right));
}
public static Node buildBST(Node node, int [] A) {
if (A == null) { return null; }
int len = A.length;
for (int i=0; i<len; i++) {
node = insertIntoBST(node, A[i]);
}
return node;
}
private static Node insertIntoBST(Node node, int value) {
if (null == node) {
return new Node(value);
}
if (value <= node.data) {
node.left = insertIntoBST(node.left, value);
} else {
node.right = insertIntoBST(node.right, value);
}
return node;
}
public static void printBSTInorder(Node node) {
if (null == node) { return ; }
if (null != node.left) {
printBSTInorder(node.left);
}
System.
out.
print(node.
data + " "); if (null != node.right) {
printBSTInorder(node.right);
}
}
}
class Node {
Node left;
Node right;
this.data = data;
this.left = null;
this.right = null;
}
}
Y2xhc3MgQlNUIHsKIHByaXZhdGUgc3RhdGljIE5vZGUgcm9vdDsKICAKIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZyBbXSBhcmdzKSB7CiAgaW50IFtdIEEgPSB7OCwgMywgMTAsIDEsIDYsIDE0LCA0LCA3LCAxM307CiAgcm9vdCA9IGJ1aWxkQlNUKHJvb3QsIEEpOwogIFN5c3RlbS5vdXQucHJpbnRsbigiaW5vcmRlcjogIik7CiAgcHJpbnRCU1RJbm9yZGVyKHJvb3QpOwogIFN5c3RlbS5vdXQucHJpbnRsbigpOwogIGludCBzaXplQlNUID0gc2l6ZU9mQlNUKHJvb3QpOwogIFN5c3RlbS5vdXQucHJpbnRsbigiU2l6ZSBvZiBCU1Q6ICIgKyBzaXplQlNUKTsKICAgCiAgZm9yIChpbnQgaT0xOyBpPD1zaXplQlNUOyBpKyspIHsKICAgTm9kZSBub2RlID0gbnRoTGFyZ2VzdE5vZGUocm9vdCwgaSk7CiAgIFN5c3RlbS5vdXQucHJpbnRsbihpICsgIiBsYXJnZXN0IG5vZGU6ICIgKyBub2RlLmRhdGEpOwogIH0KIH0KICAKIHB1YmxpYyBzdGF0aWMgTm9kZSBudGhMYXJnZXN0Tm9kZShOb2RlIG5vZGUsIGludCBOKSB7CiAgIGlmIChudWxsID09IG5vZGUpIAogIHsKICAgcmV0dXJuIG51bGw7CiAgfQogICAgCiAgaW50IFIgPSBzaXplT2ZCU1Qobm9kZS5yaWdodCkgKyAxOwogIGlmIChOID09IFIpIAogIHsKICAgcmV0dXJuIG5vZGU7CiAgfQogIGlmKE4gPCBSKSAKICB7CiAgIHJldHVybiBudGhMYXJnZXN0Tm9kZShub2RlLnJpZ2h0LCBOKTsKICB9IAogIGVsc2UgCiAgewogICByZXR1cm4gbnRoTGFyZ2VzdE5vZGUobm9kZS5yaWdodCwgTi1SKTsKICB9CiAgfQogCiAgCiBwdWJsaWMgc3RhdGljIGludCBzaXplT2ZCU1QoTm9kZSBub2RlKSB7CiAgaWYgKG51bGwgPT0gbm9kZSkgeyByZXR1cm4gMDsgfQogIHJldHVybiAoc2l6ZU9mQlNUKG5vZGUubGVmdCkgKyAxICsgc2l6ZU9mQlNUKG5vZGUucmlnaHQpKTsKIH0KICAKIHB1YmxpYyBzdGF0aWMgTm9kZSBidWlsZEJTVChOb2RlIG5vZGUsIGludCBbXSBBKSB7CiAgaWYgKEEgPT0gbnVsbCkgeyByZXR1cm4gbnVsbDsgfQogIGludCBsZW4gPSBBLmxlbmd0aDsKICBmb3IgKGludCBpPTA7IGk8bGVuOyBpKyspIHsKICAgbm9kZSA9IGluc2VydEludG9CU1Qobm9kZSwgQVtpXSk7CiAgfQogIHJldHVybiBub2RlOwogfQogIAogcHJpdmF0ZSBzdGF0aWMgTm9kZSBpbnNlcnRJbnRvQlNUKE5vZGUgbm9kZSwgaW50IHZhbHVlKSB7CiAgaWYgKG51bGwgPT0gbm9kZSkgewogICByZXR1cm4gbmV3IE5vZGUodmFsdWUpOwogIH0KICBpZiAodmFsdWUgPD0gbm9kZS5kYXRhKSB7CiAgIG5vZGUubGVmdCA9IGluc2VydEludG9CU1Qobm9kZS5sZWZ0LCB2YWx1ZSk7CiAgfSBlbHNlIHsKICAgbm9kZS5yaWdodCA9IGluc2VydEludG9CU1Qobm9kZS5yaWdodCwgdmFsdWUpOwogIH0KICByZXR1cm4gbm9kZTsKIH0KICAKIHB1YmxpYyBzdGF0aWMgdm9pZCBwcmludEJTVElub3JkZXIoTm9kZSBub2RlKSB7CiAgaWYgKG51bGwgPT0gbm9kZSkgeyAgcmV0dXJuIDsgfQogIGlmIChudWxsICE9IG5vZGUubGVmdCkgewogICBwcmludEJTVElub3JkZXIobm9kZS5sZWZ0KTsKICB9CiAgU3lzdGVtLm91dC5wcmludChub2RlLmRhdGEgKyAiICIpOwogIGlmIChudWxsICE9IG5vZGUucmlnaHQpIHsKICAgcHJpbnRCU1RJbm9yZGVyKG5vZGUucmlnaHQpOwogIH0KIH0KfQogCmNsYXNzIE5vZGUgewogSW50ZWdlciBkYXRhOwogTm9kZSBsZWZ0OwogTm9kZSByaWdodDsKICAKIHB1YmxpYyBOb2RlKEludGVnZXIgZGF0YSkgewogIHRoaXMuZGF0YSA9IGRhdGE7CiAgdGhpcy5sZWZ0ID0gbnVsbDsKICB0aGlzLnJpZ2h0ID0gbnVsbDsKIH0KfQ==