Question

PROBLEM 6:

Suppose we insert keys below into an initially empty Vanilla binary search tree in the given order:

6, 9, 2, 1, 5, 7, 10, 8, 3, 4

(a) Draw the resulting binary search tree.

(b) List the keys according to:

A pre-order traversal

An in-order traversal

A post-order traversal

(c) Now we perform some deletions using the “deletion by copying” strategy in which promoted keys are always drawn from a node’s right subtree (so that there is only one correct answer).

(i) Simulate the deletion of 2 and draw the resulting tree. State any relevant assumptions.

(ii) Now (on the resulting tree) simulate the deletion of 6 and draw the resulting tree. Again, stating any relevant assumptions.

Answer 1

i) Binary Search Tree

ii) A pre-order traversal: ROOT - LEFT - RIGHT
6 2 1 5 3 4 9 7 8 10

iii) An in-order traversal: LEFT - ROOT - RIGHT
1 2 3 4 5 6 7 8 9 10

iv) A post-order traversal: LEFT - RIGHT - ROOT
1 4 3 5 2 8 7 10 9 6

--------------------------------------

We are allowed to answer 4 sub parts only. Please post accordingly.