2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Does every node of the tree have three children? $\endgroup$ – Jack M Jan 26 '16 at 18:05
  • $\begingroup$ 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) ) $\endgroup$ – ALL Jan 26 '16 at 19:19
2
$\begingroup$

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!

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thank you, this worked like a charm! I knew I was really close. $\endgroup$ – ALL Jan 26 '16 at 21:19

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.