public class KthLargest {
	public static void main(String[] args) {
		//Tree must be sorted, smaller values on the left.
		Node root =
			new Node(15,
				new Node(12,
					new Node(6),
					new Node(14)
				),
				new Node(40,
					new Node(25),
					new Node(80)
				)
			);

		for (int k = 1; k <= size(root); ++k) {
			System.out.println(kthLargest(root, k));
		}

		System.exit(0);
	}

	private static int size(Node node) {
		if (node == null) {
			return 0;
		}
		return size(node.left) + size(node.right) + 1;

		//return node == null ? 0 : size(node.left) + size(node.right) + 1;
	}

	private static int kthLargest(Node node, int k) {
		if (k <= size(node.right)) {
			return kthLargest(node.right, k);
		}
		if (k == size(node.right) + 1) {
			return node.value;
		}
		return kthLargest(node.left, k - size(node.right) - 1);

		/*
		return k <= size(node.right)        ? kthLargest(node.right, k)
			: k == size(node.right) + 1 ? k
			                            : kthLargest(node.left, k - size(node.right) - 1);
		*/
	}
}

class Node {
	int value;
	Node left;
	Node right;

	Node(int value, Node left, Node right) {
		this.value = value;
		this.left = left;
		this.right = right;
	}

	Node(int value) {
		this.value = value;
		//this.left and this.right implicitly initialized to null
	}
};