- Linked lists and binary trees are examples of dynamic data structures.
(a) (i) Outline one benefit of using dynamic data structures. [2]
(ii) Outline one drawback of using dynamic data structures. [2]
Figure 3 represents a linked list containing the numbers 6, 15, 21 and 30.
linked list diagram showing nodes 6 → 15 → 21 → 30 → null
(b) Describe the steps to find and delete the node containing data item 21. [5]
(c) Describe the structure of a node in a binary tree. [2]
These numbers are input in the following order: 18 15 25 6 2 21 36 30 40 and inserted in a binary tree such that an inorder traversal of the binary tree outputs the numbers sorted in ascending order.
(d) (i) Sketch the resulting binary tree. [3]
(ii) State all the leaf nodes in the binary tree sketched in part (d)(i). [1]