Binary trees
A car dealership’s stock control system stores details of cars in a binary tree structure. The tree
structure uses manufacturers’ names as key values.
(a) Draw a representation of the binary tree using the following key values in this order:
Peugeot, Ford, Vauxhall, Mercedes, BMW, Audi, Renault, Toyota. [3]
(b) Add Jaguar to the binary tree. [1]
(c) List the key values sorted in the order that a post-order traversal of the tree would produce. [2]
A binary tree structure is designed to contain strings and uses the following rules:
● The left pointer indicates the condition “earlier or at the same position in the alphabet”
● The right pointer indicates the condition “later in the alphabet”
Construct a binary tree using these rules and the data entered in the following order:
Goat, Duck, Fox, Bear, Ant, Cat, Leopard, Owl, Mayfly, Insect, Jaguar, Emu.
(b) Carry out a pre-order traversal of the tree and give one use of pre-order traversals. [2]
● GDBACFELIJOM
● Use
7
, ○ Clone a tree
○ Count the number of leaves
○ Convert expression tree to prefix notation
(c) Carry out an in-order traversal of the tree and give one use of in-order traversals. [2]
● ABCDEFGIJLMO
● Sort/search a binary tree
(d) Carry out a post-order traversal of the tree and give one use of post-order traversals. [2]
● ACBEFDJIMOLG
● Use
○ Deleting / Undo a binary tree
○ Stack-based programming
○ Convert postfix notation to expression tree
A cloud storage solution uses binary trees for its file system. The file structures can be traversed
using a variety of methods. Describe the following methods of traversal and give an example of
how each method could be used in the file system.
In-order traversal [3] - In-order traversal is applied by visiting the left subtree first, then root and
finally the right subtree. This method could be when searching for a file in the file system
Post-order traversal [3] - Post-order traversal is applied by visiting the left subtree first, then right
subtree and finally the root. This method could be used to delete all files in the file system.
Pre-order traversal - Pre-order traversal is applied by visiting the root first, then left subtree and
finally the right subtree. This method could be used to create copy files in the file system.
Draw a representation of a binary tree using the data items from question 11(b) as key values. [3]
8
