given an AVL tree with $size$ value to any vertex $v$ in the tree (which is the size of the tree rooted in $v$), is it possible to tell for a given value in the tree, what its order in the sorted group in $log (n)$ time complexity?


1 Answer 1


Searching for the value in the tree is a $O(\log n)$ task.

Then, we can visit the path leading to the value, from the leaf (the value), to the root. At every intermediate node, we know how many other values there are further on the left: none, if we moved up from the left subtree, and left.size (which is assumed to be stored in each node) otherwise.

So, we can add all the relevant size values, counting up how many other values we have on the left of our value, so retrieving the order of the value in $O(\log n)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.