# Find height of a ternary tree

Ternary heap is like a binary tree, just every node can have up to $$3$$ sons and not $$2$$.

I try to bound the number of nodes in the heap, $$n$$, using the height of the heap $$h$$.

The solutions get to:

$$3^h < n < 3^{h+1}$$

Yet, I get to:

$$\frac{3^h}{2} < n < \frac{3^{h+1}}{2}$$

In short, what I do is:

$$\sum_{i = 0}^{h - 1}3^i = \frac{3^h-1}{2}$$

For all the nodes in all levels except for the last level, because all the levels are full.

If the last level is full:

$$\frac{3^h - 1}{2} + 3^h$$

If the last level has only $$1$$ node, we get:

$$\frac{3^h - 1}{2} + 1$$

From here I conclude what I showed at the beginning.

Why the solutions get to something else?

## 1 Answer

The expected solution is wrong.

Pick $$h=0$$. The only ternary heap with height $$0$$ has only one node. Nevertheless the expected solution says that it needs to have at least $$3^0 + 1 = 2$$ nodes.

In case you meant to write $$3^h \le n \le 3^{h+1}$$ instead of $$3^h < n < 3^{h+1}$$, the expected solution is still wrong. Consider a ternary heap with $$n=2$$ nodes. This heap has height $$1$$ but according the expected solution it should have at least $$3^h = 3$$ nodes.

• So the height of a ternary tree is $h = \left \lfloor log_32n \right \rfloor$?
– Alon
Commented May 27, 2020 at 19:52
• Yes.$\phantom{}$ Commented May 27, 2020 at 20:13