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)
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
A quicker route: for a full binary tree, if there are \(I\) internal nodes, there are always \(I+1\) leaves, so total nodes \(N = 2I+1\), which means \(I = (N-1)/2\).
For \(N = 23\): \(I = (23-1)/2 = 11\) internal nodes and \(12\) leaves.
Now think about how tall this tree can get. Height is maximized when the tree is stretched into one long chain instead of being built wide and bushy. Picture a spine of internal nodes going straight down, where each spine node peels off exactly one leaf to the side, except the very last spine node, which ends in two leaves because it still needs 2 children to remain a full node and there is no more spine to continue.
With 11 internal nodes forming this spine, the last spine node sits at depth 10, and its two leaf children sit at depth 11. So the longest path from root to leaf has 11 edges, i.e. height 11. Since every internal node is used purely to extend the chain by one more level, this is the tallest arrangement possible with 11 internal nodes.
Hence the maximum possible height is \(11\).
Top Questions on Trees
- 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}
- In a B+- tree where each node can hold at most four key values, a root to leaf path consists of the following nodes: \( A = (49, 77, 83, -) \)
\( B = (7, 19, 33, 44) \)
\( C = (20^*, 22^*, 25^*, 26^*) \)
The *-marked keys signify that these are data entries in a leaf. Assume that a pointer between keys \( k_1 \) and \( k_2 \) points to a subtree containing keys in \([ k_1, k_2 )\), and that when a leaf is created, the smallest key in it is copied up into its parent. A record with key value 23 is inserted into the B+- tree. The smallest key value in the parent of the leaf that contains 25* is ___________ . (Answer in integer) - Suppose the values 10, β4, 15, 30, 20, 5, 60, 19 are inserted in that order into an initially empty binary search tree. Let \( T \) be the resulting binary search tree. The number of edges in the path from the node containing 19 to the root node of \( T \) is \underline{{1cm}}. {(Answer in integer)}
- A binary search tree \( T \) contains \( n \) distinct elements. What is the time complexity of picking an element in \( T \) that is smaller than the maximum element in \( T \)?
- Want to practice more? Try solving extra ecology questions todayView All Questions
Questions Asked in GATE CS exam
A database has 25,000 fixed-length records of 100 bytes (primary key 15 bytes). The data file is block-aligned so each record is fully contained within a block. The file is indexed by a primary index file, also block-aligned and ordered. Block size is 1024 bytes and a block pointer is 5 bytes. Each index entry stores the blockβs anchor key (15 bytes) and a pointer (5 bytes). Binary search on an index file of \(b\) blocks needs \(\lceil \log_2 b \rceil\) block accesses in the worst case. Given a key, the number of block accesses required to identify the data file block that may contain the record, in the worst case, is ____________.
- GATE CS - 2023
- Database Management Systems