Register

GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 16

• retagged by
566 views
6 votes
6 votes

Suppose we constructed the binary search tree shown by starting with an empty tree and inserting one element at a time from an input sequence, without any rotations or other manipulations. Which of the following assertions about the order of elements in the input sequence can NOT  be true?

  1. $8$ came after $3$ and $19$ came after $29.$
  2. $7$ came before $8$ and $23$ came after $37.$
  3. $1$ came after $12$ and $29$ came before $42.$
  4. $3$ came before $14$ and $16$ came before $28.$
• retagged by
User Avatar

1 Answer

6 votes
6 votes
$28$ is an ancestor of $16,$ so $16$ must have come after $28.$ In the tree, only ancestor-descendant relationships matter in determining the order in which elements arrive. An ancestor must always come before any of its descendants. Incomparable elements could come in any order.
• edited by
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

618
views
1 answers
3 votes
GO Classes asked Jan 28
618 views
GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 17
Suppose that a binary min-heap stores six elements with priorities $10,20,30,40,50$, and $60$ in its array $\text{A}.$ What is the largest of these items that could be stored in $\text{A}[2]?$ (indexing starts from zero)
User Avatar
490
views
1 answers
3 votes
GO Classes asked Jan 28
490 views
GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 36
Let $\mathrm{T}$ be the smallest AVL tree of height $h$. How many nodes does it have, if the smallest AVL tree of height $h-2$ has $m$ nodes and the smallest AVL tree of height $h-3$ has $k$ nodes?$m+k+2$m+2 k$2 m+k$2 m+k+2$
User Avatar
560
views
2 answers
4 votes
GO Classes asked Jan 28
560 views
GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 37
Consider the null-terminated linked list of four integers $\textsf{1->2->3->4->NULL},$ and the variable 'list' points to the head of the linked list. Upon running the ... ->next->next>next = list->next>next; LINE Y: list = list->next->next;
User Avatar
963
views
3 answers
7 votes
GO Classes asked Jan 28
963 views
GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 40
You are given a complete binary tree (each level must be full except the last) on $n$ vertices. Each vertex $v$ is labeled by an integer value $x_v$. Say that a vertex is a ... $\theta(\sqrt{n})$\theta(\log n)$\theta(n \log n)$
User Avatar
Link Copied!