Question:
Let \(P\) be the set of all integers from 1 to 15. Consider any order of insertion of the elements of \(P\) 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 \(P\) be the set of all integers from 1 to 15. Consider any order of insertion of the elements of \(P\) 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?
Which one of the following elements can NEVER be the third element that is inserted?
Show Hint
Work out the unique shape of the complete (here, perfect) binary search tree that 1 to 15 must form, then check how many ancestors each candidate value has, since every ancestor of a node must be inserted before it.
Updated On: Jul 22, 2026
- 4
- 2
- 10
- 5
Show Solution
Verified By Collegedunia
The Correct Option is D
Solution and Explanation
Step 1: Determine the unique shape forced by the problem.
A binary search tree with 15 nodes that is also a complete binary tree must, in fact, be a perfect binary tree of height 4, since \(2^4-1=15\) is exactly the node count that fills every level completely (a complete tree with 15 nodes has no room for a partially filled last level). In a binary search tree, an in order traversal always visits the keys in sorted order, so the in order traversal of this tree must be \(1,2,3,\dots,15\).
Step 2: Reconstruct the tree from the sorted sequence.
In a perfect binary search tree, the root splits the sorted sequence into two equal halves, and this rule applies recursively:
Root (level 1): median of 1 to 15 is 8.
Level 2: median of 1 to 7 is 4 (left subtree root); median of 9 to 15 is 12 (right subtree root).
Level 3: median of 1 to 3 is 2; median of 5 to 7 is 6; median of 9 to 11 is 10; median of 13 to 15 is 14.
Level 4 (leaves): 1, 3 (children of 2); 5, 7 (children of 6); 9, 11 (children of 10); 13, 15 (children of 14).
This shape is forced and unique.
Step 3: Use the key property of sequential BST insertion.
When keys are inserted one at a time into an initially empty binary search tree, a node can only be inserted into the tree once its parent already exists in the tree, because the insertion path must pass through the parent to find the correct empty child slot. So every ancestor of a node in the final tree must have been inserted strictly before that node, in every valid insertion order that produces this shape. In particular, the root itself must always be the first element inserted.
Step 4: Count the ancestors of each candidate value.
Value 4: ancestors are just {8}, a level 2 node.
Value 2: ancestors are {8, 4}, a level 3 node.
Value 10: ancestors are {8, 12}, a level 3 node.
Value 5: ancestors are {8, 4, 6}, since the path from the root is 8 to 4 to 6 to 5, a level 4 (leaf) node.
Step 5: Check whether each value can be the third insertion.
For value 4 (1 ancestor): insert 8 first, then 12 second, then 4 third; since 4<8, it correctly becomes the left child of the root. This is valid, so 4 CAN be third; option (A) is achievable.
For value 2 (2 ancestors, 8 and 4): insert 8 first, 4 second (left child of root), then 2 third (correctly becomes left child of 4). Valid, so 2 CAN be third; option (B) is achievable.
For value 10 (2 ancestors, 8 and 12): insert 8 first, 12 second, 10 third; valid, so 10 CAN be third; option (C) is achievable.
For value 5 (3 ancestors, 8, 4 and 6): to insert 5 at all, both 4 and 6 must already be present in the tree in addition to the root 8, since the search path for 5 is root(8) to 4 to 6 to the empty slot for 5. That requires 8, 4 and 6 to occupy three separate earlier insertion slots before 5 can be inserted at all. So the earliest possible position for 5 in any valid insertion order is the 4th insertion. Value 5 can therefore never be the third element inserted.
Step 6: Conclusion.
Only option (D), value 5, is impossible as the third inserted element.\[ \boxed{5 \ \text{(Option D)}} \]
A binary search tree with 15 nodes that is also a complete binary tree must, in fact, be a perfect binary tree of height 4, since \(2^4-1=15\) is exactly the node count that fills every level completely (a complete tree with 15 nodes has no room for a partially filled last level). In a binary search tree, an in order traversal always visits the keys in sorted order, so the in order traversal of this tree must be \(1,2,3,\dots,15\).
Step 2: Reconstruct the tree from the sorted sequence.
In a perfect binary search tree, the root splits the sorted sequence into two equal halves, and this rule applies recursively:
Root (level 1): median of 1 to 15 is 8.
Level 2: median of 1 to 7 is 4 (left subtree root); median of 9 to 15 is 12 (right subtree root).
Level 3: median of 1 to 3 is 2; median of 5 to 7 is 6; median of 9 to 11 is 10; median of 13 to 15 is 14.
Level 4 (leaves): 1, 3 (children of 2); 5, 7 (children of 6); 9, 11 (children of 10); 13, 15 (children of 14).
This shape is forced and unique.
Step 3: Use the key property of sequential BST insertion.
When keys are inserted one at a time into an initially empty binary search tree, a node can only be inserted into the tree once its parent already exists in the tree, because the insertion path must pass through the parent to find the correct empty child slot. So every ancestor of a node in the final tree must have been inserted strictly before that node, in every valid insertion order that produces this shape. In particular, the root itself must always be the first element inserted.
Step 4: Count the ancestors of each candidate value.
Value 4: ancestors are just {8}, a level 2 node.
Value 2: ancestors are {8, 4}, a level 3 node.
Value 10: ancestors are {8, 12}, a level 3 node.
Value 5: ancestors are {8, 4, 6}, since the path from the root is 8 to 4 to 6 to 5, a level 4 (leaf) node.
Step 5: Check whether each value can be the third insertion.
For value 4 (1 ancestor): insert 8 first, then 12 second, then 4 third; since 4<8, it correctly becomes the left child of the root. This is valid, so 4 CAN be third; option (A) is achievable.
For value 2 (2 ancestors, 8 and 4): insert 8 first, 4 second (left child of root), then 2 third (correctly becomes left child of 4). Valid, so 2 CAN be third; option (B) is achievable.
For value 10 (2 ancestors, 8 and 12): insert 8 first, 12 second, 10 third; valid, so 10 CAN be third; option (C) is achievable.
For value 5 (3 ancestors, 8, 4 and 6): to insert 5 at all, both 4 and 6 must already be present in the tree in addition to the root 8, since the search path for 5 is root(8) to 4 to 6 to the empty slot for 5. That requires 8, 4 and 6 to occupy three separate earlier insertion slots before 5 can be inserted at all. So the earliest possible position for 5 in any valid insertion order is the 4th insertion. Value 5 can therefore never be the third element inserted.
Step 6: Conclusion.
Only option (D), value 5, is impossible as the third inserted element.\[ \boxed{5 \ \text{(Option D)}} \]
Was this answer helpful?
0
0
Top GATE CS Programming and Data Structures Questions
- Which of the following sequences when stored in an array at locations A[1],..., A[10] forms a max-heap?
- Given N distinct elements in an array, determine the number of comparisons required to find the element which is not the largest:
Consider the following code:
main() { int x = 126, y = 105; { if (x > y) x = x - y; else y = y - x; } while (x != y) printf("%d", x); }- In a binary search tree with the following elements: \( 10, -4, 15, 13, 20, 5, 16, 19 \), the number of edges from node 19 to the root is?
Consider the following code:
int a; int arr[] = {30, 50, 10}; int *ptr = arr[10] + 1; a = *ptr; (*ptr)++; ptr = ptr + 1; printf("%d", a + arr[1] + *ptr);
View More Questions
Top GATE CS Binary Search Trees - Insertion Order and Tree Shape Questions
Top GATE CS Questions
- Which of the following sequences when stored in an array at locations A[1],..., A[10] forms a max-heap?
- The Lucas sequence Ln is defined by the recurrence relation: Ln = Ln−1 + Ln−2, for n ≥ 3, with L1 = 1 and L2 = 3. Which one of the options given is TRUE?
- Which of the following fields of IP header is/are always modified by any router before it forwards to IP Packet ?
- Which one of the following CIDR profix exactly represent the range of IP addresses 10.12.2.0 to 10.12.3.255?
- Consider an ethernet segment whose transmission is \(10^8\) bits per second. Maximum segment length \(500\ m\), speed of the provocation media velocity is \(2 × 10^8\) meter per second. What is the minimum frame size in bits ?
View More Questions