$n$ nodes?
-
What configuration should the tree have in order to have the maximum depth?
-
… that is, in order to be as tall as possible?
-
What configuration should the tree have in order to have the minimum depth?
-
… that is, in order to be as wide as possible?
-
For the minimum case, how many nodes are there at depth
$i$from the top? -
… what can you say about the relationship between the number of nodes at depth
$i$and depth$i-1?$ -
… and what about the total sum of the nodes in this particular configuration?
-
… an arbitrary
$n$means the last row isn’t necessarily completely filled, hence$n$is only upper bounded rather than equal to the above sum. How can you extract the depth$d$from this inequality?
-
Maximum depth is achieved when all nodes are in a line, so there is only one node at each particular depth. Hence the maximum depth is
$n.$Minimum is achieved by making the tree as wide as possible, i.e. when each node has 3 children. The maximum number of nodes at depth
$i$is$3^i,$until we reach a sum of$n.$So, for a total depth$d$we have:$$ \begin{aligned} n &\leq \sum_{i=0}^{d}3^i \\ &= \frac{3^d - 1}{3 - 1}. \end{aligned} $$This rearranges to$d \geq \log_3(2n+1).$We want the smallest such integer (next largest integer), which means$d= \lceil \log_3(2n+1) \rceil,$where$\lceil \cdot \rceil$is the ceiling function.Note: counting either nodes or edges would be acceptable as a correct answer.