How can I calculate the level of a node in a perfect binary tree from its depth-first order index?

Question

I have a perfect binary tree, i.e. each node in the tree is either a leaf node, or has two children, and all leaf nodes are on the same level. Each node has an index in depth-first order.

(E.g. in a tree with 3 levels the root node has index 0, the first child has 1, the first child of the first child has 2, the second child of the first child has 3, the second child has 4, the first child of the second child has 5, the second child of the second child has index 6.

      0
    /   \
  1      4
 / \    / \
2   3  5   6

)

I know the size of tree (number of nodes/maximum level), but only the index of a particular node, and I need to calculate its level (i.e. its distance to the rootnode). How do I do this most efficiently?

Answer 1

Here is another suggestion that would make the solution to this question easier:

If you label the nodes with an index in breadth-first order, you can compute the level without any traversal in O(1) time. So if you are doing multiple queries, you can do an O(N) BFT and have each query answered in O(1) time.

The formula for the level is:

level = floor(log(index + 1))

Where the log is to the base 2

Try it out on this tree:

       0
     /    \
    /      \
   1        2
  / \      / \
 /   \    /   \
3     4  5     6

Cheers.