A binary search tree is stored in an array of records. Each record has a Left pointer, a Data field and a Right pointer. A pointer value of −1 means there is no child. Items are inserted using alphabetical order: an item that comes before a node's data goes to the left of that node and an item that comes after it goes to the right. The items are inserted in the following order, with Mango as the root at index 0 and each later item stored at the next index:
Mango, Cherry, Peach, Apple, Fig, Plum, Banana, Kiwi
(a) Complete the Left and Right pointers in the table. [3]
| Index | Left | Data | Right |
|---|---|---|---|
| 0 | Mango | ||
| 1 | Cherry | ||
| 2 | Peach | ||
| 3 | Apple | ||
| 4 | Fig | ||
| 5 | Plum | ||
| 6 | Banana | ||
| 7 | Kiwi |
(b) Describe how the tree would be searched to determine whether Grape is stored in it, stating the items compared. [2]
- (a) Index 0 (Mango): Left 1, Right 2(1)
- (a) Index 1 (Cherry): Left 3, Right 4; index 2 (Peach): Left −1, Right 5(1)
- (a) Index 3 (Apple): Right 6; index 4 (Fig): Right 7; all other pointers −1(1)
- (b) Start at root and compare: Grape < Mango so go left; Grape > Cherry so go right; Grape > Fig so go right(1)
- (b) Items compared are Mango, Cherry, Fig, Kiwi; Grape < Kiwi and Kiwi's left pointer is −1 so Grape is not in the tree(1)
- Answer: (a) 0: L1 R2; 1: L3 R4; 2: L−1 R5; 3: L−1 R6; 4: L−1 R7; 5, 6, 7: L−1 R−1 (b) Compare Mango (left), Cherry (right), Fig (right), Kiwi (left = −1) – not found.
- Examiner tip: Every insertion starts again from the root – Banana goes Mango → Cherry → Apple → right of Apple.