Advanced Algorithms and Recursion: Question 4

Syllabus 19.1, 19.2

Structured A2 8 marks

A binary search tree (BST) stores integer values so that, for every node, all values in its left subtree are smaller than the node's value and all values in its right subtree are larger. Nodes are implemented using pointers:

TYPE TreeNode
    DECLARE NodeValue : INTEGER
    DECLARE LeftPointer : INTEGER
    DECLARE RightPointer : INTEGER
ENDTYPE

DECLARE Tree : ARRAY[1:10] OF TreeNode
DECLARE RootPointer : INTEGER

LeftPointer and RightPointer hold the array index of a node's left/right child, or -1 if that child does not exist. To insert a new value, the tree is searched starting from RootPointer: at each node, if the new value is smaller than that node's value the search moves to LeftPointer; if larger, it moves to RightPointer; when a pointer of -1 is reached, a new node holding the value is created there.

The values 50, 25, 75, 10, 30, 60, 90 are inserted, in that order, into an initially empty tree.

This recursive procedure then performs an in-order traversal of the tree, starting with CALL InOrder(RootPointer):

PROCEDURE InOrder(P : INTEGER)
    IF P <> -1 THEN
        CALL InOrder(Tree[P].LeftPointer)
        OUTPUT Tree[P].NodeValue
        CALL InOrder(Tree[P].RightPointer)
    ENDIF
ENDPROCEDURE

(a) Describe the structure of the resulting tree after all seven values have been inserted, stating each node's parent, and whether it is a left or right child of that parent. [3]

(b) State the sequence of values output by CALL InOrder(RootPointer), and explain why an in-order traversal of a binary search tree always produces a sequence of this kind. [3]

(c) State the sequence of values that would be produced by a pre-order traversal, and by a post-order traversal, of the same tree. [2]

Show worked solution Hide worked solution

Part (a): Building the tree

Each value is inserted by comparing it against the current node and moving left (smaller) or right (larger) until an empty (-1) pointer is reached:

50: tree is empty, so 50 becomes the root.
25: 25 < 50, go left of 50; left pointer is empty, so 25 becomes the left child of 50.
75: 75 > 50, go right of 50; right pointer is empty, so 75 becomes the right child of 50.
10: 10 < 50, go left (to 25); 10 < 25, go left of 25; empty, so 10 becomes the left child of 25.
30: 30 < 50, go left (to 25); 30 > 25, go right of 25; empty, so 30 becomes the right child of 25.
60: 60 > 50, go right (to 75); 60 < 75, go left of 75; empty, so 60 becomes the left child of 75.
90: 90 > 50, go right (to 75); 90 > 75, go right of 75; empty, so 90 becomes the right child of 75.

Resulting structure:

                50
              /    \
            25      75
           /  \     /  \
         10   30  60   90

[3 marks]: [1] for correctly placing 25 and 75 as children of 50, [1] for correctly placing 10 and 30 as children of 25, [1] for correctly placing 60 and 90 as children of 75.

Part (b): In-order traversal

InOrder visits, for any node: its left subtree, then the node itself, then its right subtree. Applying this recursively from the root (50):

InOrder on the left subtree of 50 (rooted at 25) first fully completes: InOrder(10) outputs 10 (10 has no children); then 25 itself is output; then InOrder(30) outputs 30. This subtree outputs: 10, 25, 30.
50 itself is then output.
InOrder on the right subtree of 50 (rooted at 75) then runs: InOrder(60) outputs 60; then 75 itself is output; then InOrder(90) outputs 90. This subtree outputs: 60, 75, 90.

Full sequence: 10, 25, 30, 50, 60, 75, 90, which is sorted in ascending order.

This is not a coincidence: at every node in a binary search tree, everything in its left subtree is smaller and everything in its right subtree is larger, by definition. Because InOrder always visits the whole left subtree before the node and the whole right subtree after it, values are guaranteed to come out smallest-first at every level, giving a fully sorted sequence overall.

[3 marks]: [1] for the correct sequence of seven values, [1] for identifying that the sequence is sorted, [1] for a valid explanation linking the BST ordering rule to why in-order traversal must produce sorted output.

Part (c): Pre-order and post-order traversals

Pre-order (node, then left subtree, then right subtree): visit 50 first, then its whole left subtree (25, 10, 30, in that pre-order pattern: 25, then 10, then 30), then its whole right subtree (75, 60, 90, pre-order: 75, then 60, then 90).

Pre-order sequence: 50, 25, 10, 30, 75, 60, 90.

Post-order (left subtree, then right subtree, then node): visit the whole left subtree of 50 first (post-order of the 25-subtree: 10, then 30, then 25 itself last), then the whole right subtree (post-order of the 75-subtree: 60, then 90, then 75 itself last), then 50 itself, last of all.

Post-order sequence: 10, 30, 25, 60, 90, 75, 50.

[2 marks]: [1] for the correct pre-order sequence, [1] for the correct post-order sequence.

Final answers

(a) Root 50; left child 25, right child 75; 25’s children are 10 (left) and 30 (right); 75’s children are 60 (left) and 90 (right).
(b) In-order: 10, 25, 30, 50, 60, 75, 90 (sorted, because left-subtree values are always smaller and right-subtree values always larger at every node).
(c) Pre-order: 50, 25, 10, 30, 75, 60, 90. Post-order: 10, 30, 25, 60, 90, 75, 50.

Common mistakes

During insertion, comparing a new value only against the root (e.g. inserting 60 and 90 directly as children of 50) instead of continuing to compare against each node reached while descending, correctly moving past 50 to compare against 75.
Inserting a value on the wrong side, e.g. placing 30 as a left child instead of a right child of 25, by applying the left-is-smaller / right-is-larger rule backwards.
Confusing pre-order and post-order with in-order: outputting the root value between its two subtrees (which is in-order), rather than before both subtrees (pre-order) or after both subtrees (post-order).
Assuming the in-order sequence is only sorted if the tree happens to be perfectly balanced, rather than recognising that any correctly-built binary search tree produces a sorted in-order sequence regardless of its shape.
Omitting a leaf node from a traversal (for example forgetting 30 or 90), or listing a value more than once, rather than visiting each of the seven nodes exactly once.