Practice Paper 2 Question 7

A ternary tree is a collection of nodes, each having 0, 1, 2 or 3 children, where one node is not the child of any node and each of the other nodes is a child of exactly one other node. What are the maximum and minimum possible depths of a ternary tree containing $$n$$ nodes?

The above links are provided as is. They are not affiliated with the Climb Foundation unless otherwise specified.

Hints

• Hint 1
What configuration should the tree have in order to have the maximum depth?
• Hint 2
... that is, in order to be as tall as possible?
• Hint 3
What configuration should the tree have in order to have the minimum depth?
• Hint 4
... that is, in order to be as wide as possible?
• Hint 5
For the minimum case, how many nodes are there at depth $$i$$ from the top?
• Hint 6
... what can you say about the relationship between the number of nodes at depth $$i$$ and depth $$i-1?$$
• Hint 7
... and what about the total sum of the nodes in this particular configuration?
• Hint 8
... 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?

Solution

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{align} n &\leq \sum_{i=0}^{d}3^i \\ &= \frac{3^d - 1}{3 - 1}. \end{align} 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.

If you have queries or suggestions about the content on this page or the CSAT Practice Platform then you can write to us at oi.tasc@sulp.ecitcarp. Please do not write to this address regarding general admissions or course queries.