## Fast positions in left-complete, array based binary trees

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 *7*th 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