Find depth of three node tree

Question

I am trying to write a formula to find the depth of a three node tree and having issues doing it.

Each node will have an index number going from top to bottom, left to right.

It will look something like this:

                  0
              /   |   \
            1     2     3
           /|\   /|\   /|\
          4 5 6 7 8 9 101112

(10,11,12 are separate)

Given any of these integers, how can I find which level number it will be on the tree?

I thought it would be something like: d = ceil( log(n) / log(3) )

This is close, but it gets off by the right most number of the level above it. (example: 12 is off by 3, 39 is off by 12, exc...)

Thanks!

Answer 1

There is $1$ node in row $0$, $3$ nodes in row $1$, $9$ nodes in row $2$ etc. The total number of nodes up-to-and-including row $k$ is $\dfrac{3^{k+1}-1}{2}$, the partial sum of the geometric series. This gives $$\begin{array}{c|c|c|c|c|c|c}k&0&1&2&3\\\hline\dfrac{3^{k+1}-1}{2}&1&4&13&40\end{array}~~~\text{ etc.}$$

So for a given node $x$ you're trying to find $k$ such that $$\dfrac{3^{k}-1}{2} \le x < \dfrac{3^{k+1}-1}{2}\\ 3^{k}-1 \le 2x < 3^{k+1}-1\\ 3^{k} \le 2x+1 < 3^{k+1}\\ k\log3\le \log(2x+1)<(k+1)\log3\\ k \le \dfrac{\log(2x+1)}{\log3}<k+1$$

i.e. $k=\left\lfloor\dfrac{\log(2x+1)}{\log3}\right\rfloor$. Tada!