3. The Abstract Data Type Binary Tree is a non-linear data structure, storing items hierarchically. The following questions are about the binary tree.

(a) Using diagrams to explain your working, show how a binary search tree (BST) would be built for the following sequence of integers. Include at least three diagrams showing the tree under construction, along with the resulting fullybuilt tree. Explain the algorithm (i.e. the rules youve used at each step) to decide where to place the values in the tree.

16, 22, 50 then the first 3 unique digits from your student number (e.g. if your student number is 991234, you would use the following sequence of integers: 16, 22, 50, 9, 1, 2)

(b) The efficiency of a BST depends on its precise structure. Many different potential binary search trees exist for the same set of integers. Give an example of the best and worst structures a binary search tree can take, using the set of integers from part a). Clearly identify which is best and why, and which is worst and why.

(c) Give an example of one less efficient and one more efficient data structure than a (best-case) BST for search operations, with a brief description quantifying their average search performance in relation to a BST.

(d) Considering the tree you made in answer to a), state whether the tree is complete, and explain what this property means.