1
$\begingroup$

I have a perfect binary tree with an arbitrary depth. I have been trying to come up with an equation to describe how many times in a row a leaf node has moved the same direction. For example, the leftmost and rightmost leaf nodes will have moved the same direction every time and the innermost leaf nodes will have moved the same direction every time after the first move. You could also think of it as traveling from root to leaf, and any time you change direction, the number of times moving in the same direction resets back to 1.

I've been trying to discover a way to plug in a leaf node index and get this number. Is this possible?

enter image description here

To summarize using the picture above, I want to be able to give the function an index, e.g. 7, and get the number of times in a row it has moved the same direction, e.g. 3.

$\endgroup$
5
  • $\begingroup$ Please clarify. For example if the tree has depth 7 and your path goes LLRLRRR, what exactly would you keep track of? $\endgroup$ – paw88789 Jul 19 '18 at 19:00
  • $\begingroup$ @paw88789 In your example, the answer would be 3, because changes in direction reset the number to 1, it went R 3 times when it stops, so its the number of matching trailing chars in your example $\endgroup$ – RoryHector Jul 19 '18 at 19:31
  • $\begingroup$ In my picture, the functions would be f(1)=1, f(2)=1, f(3)=2, f(4)=1, f(5)=1, f(6)=2, f(7)=3, f(8)=1, f(9)=1, f(10)=2 ... $\endgroup$ – RoryHector Jul 19 '18 at 19:35
  • $\begingroup$ So you just count the length of the last run as you travel from root to node? $\endgroup$ – paw88789 Jul 19 '18 at 19:41
  • $\begingroup$ @paw88789 I need a mathematical equation. Yes it's easy to see in the example above and just count it for each one but a binary tree can go on for forever so I'm trying to find a generalization. $\endgroup$ – RoryHector Jul 19 '18 at 19:52
1
$\begingroup$

Count the root as level $0$. Now say you are interested in level $k$ (for some $k\ge 1$). Number the nodes in that level $0, 1, 2, ...,2^k-1$. Then convert each node number to a binary string of length $k$ (padding with leading $0$s if necessary. The length of the last run in the binary representation of the integer gives you the value you describe in your question.

This works because going left or right in the tree corresponds to a binary digit of $0$ or $1$ respectively as you travel from root to node.

So for example a node labelled $12$ in a level would be given in binary as $1100$ (possibly with some leading $0$s, which gives a value of $2$ for the number you ask to compute in your problem, since the binary value ends in a run of two symbols ($0$s in this case).

Also note you don't need the full binary representation of a number, just the rightmost run of digits. So if you use the dividing-by-two method for converting decimal to binary, you get the digits from least significant to most significant (right-to-left), and so you stop as soon as the rightmost run of bits ends.

$\endgroup$
0
$\begingroup$

Number the leaves $\ell_i$ left to right starting with zero. You can convert from your numbering $v_i$ by $\ell_i = v_i - (2^d-1)$ where $d$ is the tree depth; $d=3$ in your diagram.

Then your path metric for the first leaf is $d$. Otherwise it is $\nu_2(\ell_i)$ for $i$ even and $\nu_2(\ell_i+1)$ for $i$ odd (that is, it's the same as the subsequent even number).

$\nu_p(n)$ is the multiplicity of $p$ in $n$ - the highest power of $p$ that divides $n$.

The formula captures the run length of $1$s or $0$s at the end of the binary representation of each $\ell_i$.

$\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.