I've got a perfect binary tree that's enumerated the post-order way. An example of such tree would be
15
7 14
3 6 10 13
1 2 4 5 8 9 11 12
The size of the tree is known to me. I'm looking for a formula or a simple algorithm that would take a single number as an input (the ID of the vertex I'm interested in) and return also a single number - the ID of the parent. It's quite easy to traverse the tree from the top and get the result in O(log n). Is there a faster solution? I'm mostly interested in the leaves, so if there's a solution for the special case, bring it on too.