A Binary Search Tree (BST) is a binary tree where each node contains a value from a well-ordered set.

(a) Suppose the keys on the middle row of a standard keyboard (H, F, K, G, A, S, D, J, L) are inserted in succession into an initially empty binary search tree. Draw the tree after this sequence of insertions has been made.

(5 marks)

(b) Given the following orders of traversal of a binary tree, recreate the tree:

Postorder : G,D,B,H,I,E,F,C,A

Inorder : D,G,B,A,H,E,I,C,F

Then write the order of the nodes visited in preorder traversal.

(10 marks)

(c) Given the following infix expression:

5 (4 + 3 * 2) 4 6 * 7

i. Draw an expression tree for the expression.

(6 marks)

ii. Write the prefix equivalent of the expression and.

(2 marks)

iii. Write the postfix equivalent of the expression.