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

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.

let i be the index you are looking for and n be the total number of nodes.

This algorithm do what you want:

level = 0
while i != 0 do
    i--
    n = (n-1)/2
    i = i%n
    level++
done

0 is the index of the root, if i = 0 then you are at the good level, else you can remove the root and you obtain two subtrees n = (n-1)/2 updates the number of nodes is the new tree (which is a subtree of the old one) and i = i%n selects only the good subtree.

It seems as if walking on the tree directly should be efficient enough.

At each step of the algorithm, keep in mind the range of the indexes on the subtree of the node you are at. The first value of the range it the root node, and after that the first half is the range of the subtree on the left, and the second half should be the range of the right subtree. You can then recursively move down until you find your node.

For example, lets search for in a 4 level tree with 15 elements

                 (root node)(left elements)(right elements)
Starting range:  (0)(1 2 3 4 5 6 7)(8 9 10 11 12 13 14)
Go left       :  (1)(2 3 4)(5 6 7)
Go right      :  (5)(6)(7)
Found node, total depth 2

You should be able to do this with a simple loop, using just a couple of variables to store the start and the end of the ranges. You should also easily be able to adapt this if you do some minor changes, such as using post/pre/in-order traversal or starting the indexes form 1 instead of 0.