Question 7 of 9: Pointer-based Data Structures — Preorder Traversal and find_min_leaf

Question 7: Pointer-based Data Structures — Preorder Traversal and find_min_leaf (20 marks: (a) 10, (b) 10)

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.

Given. A binary tree of TreeNodes (corrected struct above), possibly empty (root == NULL).

Find. (a) A function printing every node's data in preorder (node, then left subtree, then right subtree), safe on an empty tree. (b) A function returning the smallest data value stored in a leaf (a node with no children) — not simply the smallest value anywhere in the tree.

Approach. Both are textbook structural recursions on the corrected struct: preorder visits the node itself before recursing into each child, with root == NULL as the base case that does nothing. find_min_leaf recurses into both children, but only returns a node's own value directly when that node has no children (is a leaf); an internal node's answer is the minimum of whichever child answers exist.

(a) Preorder traversal (10 marks)

1. Write preorder() with the empty-tree base case first.

   #include <stdio.h>    /* printf(), NULL */
   
   typedef struct treenode {
       int data;
       struct treenode *left;
       struct treenode *right;
   } TreeNode;
   
   /* Preorder traversal */
   void preorder(TreeNode *root)
   {
       if (root == NULL) return;      /* empty (sub)tree: nothing to print */
       printf("%d ", root->data);
       preorder(root->left);
       preorder(root->right);
   }

2. Trace it on a worked example tree (root 8; left child 3 with children 1 and 6, where 6 has children 4 and 7; right child 10 with right child 14, which has left child 13). Preorder visits a node, then its whole left subtree, then its whole right subtree, recursively: $$\boxed{\text{preorder} = 8,\,3,\,1,\,6,\,4,\,7,\,10,\,14,\,13}$$ and calling preorder(NULL) directly (an empty tree) prints nothing and returns immediately, as required.

(b) Smallest data value in a leaf (10 marks)

1. Recurse, but only "count" a node when it has no children.

   #include <limits.h>
   
   int find_min_leaf(TreeNode *root)
   {
       if (root == NULL) return INT_MAX;   /* identity element for a min-fold */
   
       if (root->left == NULL && root->right == NULL)
           return root->data;              /* root itself is a leaf */
   
       int left_min  = find_min_leaf(root->left);
       int right_min = find_min_leaf(root->right);
       return (left_min < right_min) ? left_min : right_min;
   }

   A single-node tree is itself a leaf (no children), so it correctly returns its own value via the leaf base case, not the empty-tree sentinel.
2. Trace it where the tree's global minimum is NOT a leaf — the case that actually exercises the distinction the question is testing. Take root 8 with left child 1 (an internal node with children 5 and 9) and right child 10 (a leaf). The overall smallest value in the whole tree is 1, but node "1" has two children, so it is not a leaf; the leaves are 5, 9 and 10, whose minimum is 5. $$\boxed{\text{find\_min\_leaf} = 5,\ \text{not } 1}$$ A naive "return the minimum value anywhere in the tree" implementation would wrongly report 1 here; restricting the base case to childless nodes is what makes 5 the correct answer.