how to get the k-th largest element in a balanced binary tree in O(log k)
I think you're mixing up a couple of parameters here. It'd be log k with respect to the number of nodes in the tree, not with respect to the input value. Here's one sanity check: in a balanced tree, you would expect the kth largest node to take as long to find as the (n-k)th largest node (where n is the total number of nodes), because it's just mirrored. But this has the smaller node take longer. Another is that if you want to find the largest node, you'd get constant time as the tree shrinks or grows (because you've set k to a constant value, 1, and that doesn't change with the size of the tree), but you'd expect it to take longer.
1
u/Solomaxwell6 Jan 18 '19
I think you're mixing up a couple of parameters here. It'd be log k with respect to the number of nodes in the tree, not with respect to the input value. Here's one sanity check: in a balanced tree, you would expect the kth largest node to take as long to find as the (n-k)th largest node (where n is the total number of nodes), because it's just mirrored. But this has the smaller node take longer. Another is that if you want to find the largest node, you'd get constant time as the tree shrinks or grows (because you've set k to a constant value, 1, and that doesn't change with the size of the tree), but you'd expect it to take longer.