- 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.
Figure 3: A linked list
(Diagram showing nodes with values 6, 15, 21, 30 and null pointer)
(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]