The height of a binary tree is the number of edges in the longest path from the root to a leaf in the tree. The maximum possible height of a full binary tree with 23 nodes is __________. (answer in integer)

Question

Consider the following algorithm tt{someAlgo that takes an undirected graph $ G $ as input.} tt{someAlgo(G)} Let $ v $ be any vertex in $ G $. Run BFS on $ G $ starting at $ v $. Let $ u $ be a vertex in $ G $ at maximum distance from $ v $ as given by the BFS. Run BFS on $ G $ again with $ u $ as the starting vertex. Let $ z $ be the vertex at maximum distance from $ u $ as given by the BFS. Output the distance between $ u $ and $ z $ in $ G $. The output of tt{someAlgo(T)} for the tree shown in the given figure is ___________ . (Answer in integer) \begin{center} \includegraphics{q59_fig.png} \end{center}

Answer 1

Approach this from the node-count bounds of a full binary tree of height $h$.

In any full binary tree every internal node has exactly two children, so the total node count $N$ is always odd, and for $N = 23$ nodes the tree has $I = 11$ internal nodes and $L = 12$ leaves, since $N = 2I + 1$.
For a fixed height $h$, the smallest full binary tree that reaches that height is a long thin spine where each internal node on the spine sends one child straight down to continue the path and the other child is a leaf that ends immediately. This uses exactly $2h + 1$ nodes: check $h = 0$ gives 1 node (just a leaf root, trivial), $h = 1$ gives 3 nodes, $h = 2$ gives 5 nodes, and so on, increasing by 2 nodes per extra level of height.
Since real trees cannot use fewer nodes than this minimum for a given height, the tallest tree obtainable from a budget of $N$ nodes satisfies $2h + 1 \le N$, so $h \le \dfrac{N-1}{2}$.
Plugging in $N = 23$: $h \le \dfrac{23-1}{2} = 11$, and this bound is tight because $2(11)+1 = 23$ uses up the node budget exactly, so a height-11 full binary tree with exactly 23 nodes really exists.

So the maximum possible height is 11.

$$\boxed{11}$$

Answer 2

Approach this from the node-count bounds of a full binary tree of height $h$.

In any full binary tree every internal node has exactly two children, so the total node count $N$ is always odd, and for $N = 23$ nodes the tree has $I = 11$ internal nodes and $L = 12$ leaves, since $N = 2I + 1$.
For a fixed height $h$, the smallest full binary tree that reaches that height is a long thin spine where each internal node on the spine sends one child straight down to continue the path and the other child is a leaf that ends immediately. This uses exactly $2h + 1$ nodes: check $h = 0$ gives 1 node (just a leaf root, trivial), $h = 1$ gives 3 nodes, $h = 2$ gives 5 nodes, and so on, increasing by 2 nodes per extra level of height.
Since real trees cannot use fewer nodes than this minimum for a given height, the tallest tree obtainable from a budget of $N$ nodes satisfies $2h + 1 \le N$, so $h \le \dfrac{N-1}{2}$.
Plugging in $N = 23$: $h \le \dfrac{23-1}{2} = 11$, and this bound is tight because $2(11)+1 = 23$ uses up the node budget exactly, so a height-11 full binary tree with exactly 23 nodes really exists.

So the maximum possible height is 11.

The height of a binary tree is the number of edges in the longest path from the root to a leaf in the tree. The maximum possible height of a full binary tree with 23 nodes is __________. (answer in integer)

Show Hint

Correct Answer: 11

Solution and Explanation

Top Questions on Trees

Questions Asked in GATE CS exam