The CSAT and Practice[+] are designed by the Climb Foundation to help candidates. We are advocates for more opportunity to shine and less opportunity to fail, and we strive to level the playing field.

The Computer Laboratory

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.foo[email protected]. Please do not write to this address regarding general admissions or course queries.