Heights series in the DFS traversal of a binary tree

Question

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.

Answer 1

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.

Answer 2

Follow the hint of @DDoSolitary and write the argument of your function (which is the number of the node you are interested in, counting in postorder) in binary. On my notepad it seemed easier to start with node number 1 (rather than 0) but it is easy to compensate that.

               1111
              /   \
            /       \
          /           \
        /               \
     111                1110
    /   \              /    \
   /     \            /      \
  11      110        1010     1101
 / \      / \       /  \      / \
1   10  100  101  1000 1001 1011 1100

If the binary number consists of $k$ ones then the result is $k-1$. Otherwise, you will have to move from the right branch of the tree to the left branch by substracting an appropriate number, and recurse. E.g., you move from 1101 to 110 and from there to 11 which gives result $1$.

Perhaps you want to figure that out yourself.

ps. https://oeis.org/A215020