Pointer-based Data Structures — Inorder Traversal: 25-Comp-A4 Program Design and Data Structures, December 2018, Q8

Question 8: Pointer-based Data Structures — Inorder Traversal (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Check: the printed TreeNode struct does not compile as given. Its left/right fields are declared struct element *, but no type named element is in scope here (and even if there were, it would be the wrong type for a self-referential tree node). This is likely a slip in the printed paper. It is fixed below to the obvious intended declaration, struct treenode *left, *right, which is what makes the type genuinely self-referential, as its own name requires.

Given. A binary tree node holding an int and two child pointers, with no ordering assumption stated (unlike a BST, nothing here requires left < node < right) — the function must work for an arbitrary binary tree shape.

Find. A function that prints every node's data in inorder (left, node, right) order, and does nothing on an empty tree.

Approach. This is a direct recursive tree walk: the base case is an empty subtree (root == NULL), and the recursive case visits the left subtree, then the node itself, then the right subtree.

State the recursive definition and implement it directly. Traversing an empty subtree does nothing, which is exactly the required empty-tree behaviour — no special-case branch is needed beyond the base case itself.

#include <stdio.h>

typedef struct treenode {
    int data;
    struct treenode *left;
    struct treenode *right;
} TreeNode;

void inorder(TreeNode *root)
{
    if (root == NULL)
        return;                 /* empty (sub)tree: nothing to print */

    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

Trace it on a worked example tree (8 at the root; left subtree rooted at 3 with children 1 and 6, 6 itself having children 4 and 7; right subtree rooted at 10 with a right child 14, which itself has a left child 13): the recursion visits 1, 3, 4, 6, 7, 8, 10, 13, 14, in that order — every node's left subtree is fully printed before the node itself, which prints before its right subtree. $$\boxed{\text{inorder} = 1,\,3,\,4,\,6,\,7,\,8,\,10,\,13,\,14}$$

Question 8 — results
Quantity	Value
Example tree inorder sequence	1, 3, 4, 6, 7, 8, 10, 13, 14
inorder(NULL)	prints nothing

Concept & Theory

Topic. Recursive tree traversal as structural induction.

Key relations. Inorder$(N)$ = Inorder$(N.\text{left})$, visit$(N)$, Inorder$(N.\text{right})$, with Inorder(empty) = no-op as the base case.

Why this works. Correctness for a tree of height $h$ follows from correctness on its two subtrees of height $search tree) produces no useful ordering of the values; it is a pure traversal-mechanics exercise here.

Common pitfall. Swapping the order of the recursive call and the print statement, which silently turns inorder into preorder or postorder; and, separately, shipping the struct definition as printed (with struct element *) without noticing it fails to compile.

Source. Cormen et al., Introduction to Algorithms, 4th ed., §12.1 (tree walks); Weiss, Data Structures and Algorithm Analysis in C, 2nd ed., §4.1–4.2 (binary trees).

Question 8 of 9: Pointer-based Data Structures — Inorder Traversal

Question 8: Pointer-based Data Structures — Inorder Traversal (20 marks)