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?
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.
Best Answer
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.