# Find depth of three node tree

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!

• Does every node of the tree have three children? – Jack M Jan 26 '16 at 18:05
• Yes, it's a tree with only and always 0 or 3 nodes unless it's the parent of the bottom right most node may have 0 to 3 nodes. (also known as balanced Breadth-first tree (BFT) ) – ALL Jan 26 '16 at 19:19

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!