0

If I have a tree like this:

{a},{b,c},{d,e,f},{g,h,i,j}

in this case we have a total of 10 nodes. Is there any equation where given "10" I can calculate how many bottom nodes there are (answer: "4" in my example)?

user997112
  • 389
  • 1
    I don't understand the tree structure. What you're calling "bottom nodes" are typically called "leaf nodes," I think, but I could be wrong. Is the idea that each node has 0, 1, or 2 kids, and $a$ has children $b,c$, with $b$ having kids $d,e$ and $c$ having child $f$, and then ... no...I just don't get it. Can I suggest a notation like {a -> b, c}, {b -> d, e}, {c -> f}, {d -> g,h}, ... as a way to make the graph stucture clearer to us? – John Hughes Jul 22 '14 at 23:23
  • Did you perhaps mean a 'pyramid' of numbers ($1$ on the top row, $2$ on the second row, ...) like in Pascals triange rather than a tree?! – Winther Jul 22 '14 at 23:33

1 Answers1

1

Recall that the $n$th triangular number is given by: $$ T_n = \frac{n(n + 1)}{2} $$ You appear to be asking for the inverse of this function. By taking the positive version of the above function's inverse, we obtain the following formula: $$ \frac{\sqrt{8n + 1} - 1}{2} $$

Indeed, for $n = 10$ nodes, we find that the number of levels is: $$ \frac{\sqrt{8(10) + 1} - 1}{2} = \frac{\sqrt{81} - 1}{2} = \frac{8}{2} = 4 $$ as desired.

Adriano
  • 41,576
  • out of curiousity how did you arrive at the second equation, from the first? – user997112 Jul 22 '14 at 23:49
  • It's found by applying the quadratic formula to: $$ n = \frac{y(y + 1)}{2} \iff \frac{1}{2}y^2 + \frac{1}{2}y - n = 0 $$ in order to solve for $y$ in terms of $n$. – Adriano Jul 22 '14 at 23:51