#### Fast positions in...

A recent question I came across when working with static left complete binary search trees. How to quickly calculate the position of the k'th element in the sorted order? Suppose our search tree is as follows nodes = [ 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15 ] 8 4 12 2 6 10 14 1 3 5 7 9 11 13 15 Then the position of the 3'rd element is 9, position of 7th element is 11. Now lets modify the question a bit further. Calculate the position of the k'th element in the sorted order, for the subtree at position p and height h k_child(p, h, k) So for the subtree at position 3 (the element 12), and height 2 (a tree with a single node has height 0), the 3'rd element is at position 13 ( the element 11). For p=3, h=1, k=3, the 3'rd element is at position 7. Generally this is done using a while loop and the fact that the left and right child positions can be calculated by 2*p, 2*p+1 and takes O(b^2), where b is the number of bits in the numbers we are working with (typically 32 bit integers) We can do a lot better, in O(b) as shown with the following C++ code snippet #define k_child(p, h, k) (((p<<h)|(k>>1))/(k&(~(k-1)))) Note: The division will be optimized to bit shifts as we are dividing by a power of 2. It's a cute little puzzle which takes a bit of time to figure out but hopefully putting this out there will help others too :D