My prof was talking about how to augment a tree to efficiently find the key with a given rank. On the way to getting the right answer (store the size of the subtree rooted at each node), he proposed augmenting each node with it's rank. That way finding the node with a certain rank is a simple binary search. But he said this wouldn't work because insertion would be $\Theta(n)$. I understand that this is because in the worst case the newly inserted node has rank 0 and so the rank of each node in the tree must be incremented by 1. What I am interested in knowing is an algorithm for computing the rank of a newly inserted node. At first I thought that if a node $n$ is inserted to the left of a leaf $l$ with rank $k$ then the rank of $n$ is $k-1$, or $k+1$ if inserted right of $l$. I found a counter example to that so I know it is not the case. So how would this be done?