Question

Note: No code required.

The binary search tree shown below was constructed by inserting a sequence of items into a empty tree.
root=5
root->left=3
root->left->right=4
root->right=9
root->right->left=7
root->right->left->left=6
root->right ->left->right=8
root->right->right=12
root->right->right->right=20

Which of the following input sequences will not produce this binary search tree?
1)5 3 4 9 12 7 8 6 20
2)5 9 3 7 6 8 4 12 20
3)5 9 7 8 6 12 20 3 4
4)5 9 7 3 8 12 6 4 20
5)5 9 3 6 7 8 4 12 20
Verify it by doing rough work below others you will get 0 marks.

Answer 1

The original Binary Search Tree

1)5 3 4 9 12 7 8 6 20

This sequence will produce the same binary tree as the one shown above. As the binary tree produce by the sequence is shown below:

2)5 9 3 7 6 8 4 12 20

This sequence will produce the same binary tree as the one given above. As the binary tree produce by the sequence is shown below

3)5 9 7 8 6 12 20 3 4

This sequence will produce the same binary tree as the one given above. As the binary tree produce by the sequence is shown below

4)5 9 7 3 8 12 6 4 20

This sequence will produce the same binary tree as the one given above. As the binary tree produce by the sequence is shown below

5) 5 9 3 6 7 8 4 12 20

This sequence will not produce the same binary tree as the one given above. As the binary tree produce by the sequence is shown below

Therefore, the answer to this question in sequence number 5.