Question 4 [15 Marks] (i) What does it mean to traverse a binary tree? Using either pseudo code or Java code, provide a detailed algorithm for post-order and pre-order traversal of a binary tree. Demonstrate how this operates, using a diagram of a binary tree with at least 9 nodes. [6]

(ii) In the context of binary trees that may be balanced or unbalanced, derive O-notation expressions for the efficiency of all of the following operations: - Traversing an unbalanced binary tree - Traversing a balanced binary tree - Computing the height of an unbalanced binary tree - Computing the height of a balanced binary tree [6]

(iii) Briefly discuss how data can be stored in a Singly Linked List in a sorted fashion (e.g. in ascending or descending order). Using appropriate diagrams and/or code, demonstrate how the operations searching and inserting would work. [3]