nth smallest element of a BST

a BST(binary search tree) T is given. how to find the nth s开发者_如何学Gomallest element of T ?

A binary search tree is effectively sorted, so you just need to go through the tree in-order and get to the nth spot. If the tree is fully balanced, you can calculate the spot to get to.

If the binary search tree is not fully balanced, then you need to do a recursive search to find the nth smallest element. This can be hugely accelerated by having each node store the number of subnodes pointed to by each of its branch pointers, effectively turning the search into a binary one. However, this add overhead on tree updates as each insertion or deletion now requires a leaf-to-root traversal to update the node counts.

Alternatively, you can keep the tree balanced, and use the above answer.