edited by
750 views
1 votes
1 votes

Suppose we constructed the binary search tree shown below 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 $cannot$ 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$.
edited by

2 Answers

1 votes
1 votes
Answer (D)

16 came before 28 is not possible because then 16 would be child of 15 and 28 would be child of 16 but in given diagram 16 is child of 28.

child cannot come before parent (ancestor) in binary search tree
Answer:

Related questions