3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ I think the time complexity is $O(\log N)$ rather than $O(N)$, it is a process similar to binary tree search. $\endgroup$ – DDoSolitary Jul 29 '17 at 6:34
  • $\begingroup$ @DDoSolitary No, $N$ is the height of the tree here. $\endgroup$ – Raphael Jul 30 '17 at 17:14
  • $\begingroup$ Oh, It's quite common to use $N$ as the number of nodes so I didn't notice the difference here. Sorry for disturbing you. $\endgroup$ – DDoSolitary Jul 31 '17 at 3:01
  • 1
    $\begingroup$ @DDoSolitary You are not disturbing Raphael for sure :) Science requires this misunderstandings and even more profound vivid discusions. Thanks indeed for your contribution to the thread DDoSolitary $\endgroup$ – Carlos Linares López Jul 31 '17 at 9:08
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.