How about this procedure (works only for static BSTs).
With every node, you maintain a pointer to another node, which exists in the sub-tree rooted at that node. Along with the pointer, you also maintain the level number of the node being pointed to (along with your level number). The root is at level 0, and levels increase as you go down the tree. Initially, the pointer at a node points back to the node itself. The invariant is that you will only ever point to a node at a lower or equal level than the level number of the node.
When you search for an element in the tree, it will either:
1. Be found at its location in the BST, or
2. Be found along a path to its location because some node along the node to root path has a pointer to this node, or
3. Not be found at all.
In either case, we first make a forward pass to find the node, and if it is found, we bubble down the pointed nodes along the root to node path for the found node. If the node was found as a result of case-2, we only bubble down till the node that was pointing to the target node (this allows us to be quick for recently accessed nodes).
If a node is going to be bubbled down to a level greater than the node itself, we delete the node from the mapping set.
If a node that has no mapping is accessed, we create a new mapping for that node, and set it to replace whatever mapping existed at the node, and bubble it up progressively.
When a node is accessed, it is bubbled up all the way to the top.