Heights series in the DFS traversal of a binary tree

Assume a binary tree of height N. All nodes have exactly 2 children and all leaves have height N. For example, the following tree has N=3:

3
           /   \
         /       \
       /           \
      2             2
    /  \          /  \
   /    \        /    \
  1      1      1      1
 / \    / \    / \    / \
0   0  0   0  0   0  0   0

When we do a depth-first traversal and note the height of each node, we get the following array (for any N>3):

[0, 0, 1, 0, 0, 1, 2, 0, 0, 1, 0, 0, 1, 2, 3, 0, 0, 1, ...]

Note how the head of the array isn't dependent on N and can go infinitely.

I'm looking for a function F that, for any index in that array, would give the corresponding value. For example:

F(2) = 1
F(4) = 0
F(6) = 2

If possible, the function shouldn't be recursive. I do no want to have to iterate through millions of elements to calculate a height at an index far in.

In each node, store the number of nodes that are in its subtree. This can be maintained efficiently during tree manipulation operations.

Then, you can find the $k$-th node of a DFS-traversal in time corresponding to its level: recurse left if the left subtree contains more than $k$ elements, recurse right if it contains more, stop if neither applies. With a simple counter, you get the level of the node you find.

This applies to trees in general.

In your special case, you already know all the numbers so just don't actually have to see the tree. "Search" for $k$ in the virtual tree where each subtree has $2^{L+1} - 1$ nodes, $L$ being the level. This gives you an $O(N)$-time algorithm, discounting the exponentiation.

StackExchange Computer Science Q#79459, answer score: 2