Question:hard
Let π be the set of all integers from 1 to 15. Consider any order of insertion of the
elements of π into a binary search tree that creates a complete binary tree.
Which one of the following elements can NEVER be the third element that is
inserted?
Let π be the set of all integers from 1 to 15. Consider any order of insertion of the
elements of π into a binary search tree that creates a complete binary tree.
Which one of the following elements can NEVER be the third element that is
inserted?
Show Hint
In BST insertion a node's parent must already be in the tree before the node itself can be inserted, so work out which fixed level (root, level 1, or level 2) each candidate value sits at in the unique complete-tree layout of 1 to 15, and check whether that level can be reached by the third insertion.
Updated On: Aug 3, 2026
- 4
- 2
- 10
- 5
Show Solution
The Correct Option is D
Solution and Explanation
Alternative approach - think in terms of tree levels. Step 1: A complete binary tree built from 15 keys via BST insertion has its levels fixed by the median-splitting rule: level 0 (root) = 8, level 1 = 4 and 12, level 2 = 2, 6, 10, 14, level 3 (leaves) = 1, 3, 5, 7, 9, 11, 13, 15. Step 2: In a BST built by successive insertions, a node can only be inserted after its parent already exists, because the insertion path always walks from the root down through existing nodes to find an empty spot. So a level-k value can only be inserted after enough prior insertions have placed its ancestor chain. Step 3: The 1st insertion can only be the level-0 node, 8. The 2nd insertion can only be a level-1 node, since a level-2 node's parent has not yet been placed after just 1 insertion. Step 4: For the 3rd insertion, the sibling level-1 node is eligible since the root already exists, and the two level-2 children of whichever level-1 node was placed second are also eligible since their parent now exists. This gives exactly six eligible values for position 3: 4, 12, 2, 6, 10, 14. Step 5: A leaf value needs its level-2 parent already inserted, which requires at least 3 prior insertions (root, a level-1 node, and the specific level-2 parent), so a leaf can be inserted 4th at the very earliest, never 3rd. Step 6: Checking the options 4, 2, 10, 5 against the eligible set: 4, 2 and 10 all belong to it, but 5 is a leaf value and does not. Final answer: 5 can never be the third element inserted, option D.
Was this answer helpful?
0
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