Question 5 of 8: Pointer-based Data Structures — Binary Tree Traversal

Question 5: Pointer-based Data Structures — Binary Tree Traversal (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 node holding an int and two child pointers, with no ordering assumption stated (unlike a BST, nothing here requires left < node < right) — both functions must work for an arbitrary binary tree shape.

Find. (a) A function that prints every node's data in inorder (left, node, right) order. (b) A function returning the largest data value stored at a leaf (a node with no children) — not simply the largest value in the tree.

Approach. Both are textbook recursive tree walks: the base case is an empty subtree (root == NULL), and the recursive case combines the two child subtrees' results with the current node according to each function's own rule (print-in-order for (a), leaf-detection-and-max for (b)).

(a) inorder traversal (10 marks)

1. State the recursive definition directly. Inorder traversal of a (possibly empty) tree is: traverse the left subtree, visit the root, traverse the right subtree — and traversing an empty subtree does nothing, which is exactly the required empty-tree behaviour.

   #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);
   }

2. Trace it on a small example tree (8 at the root; left subtree 3 with children 1 and 6, 6 having children 4 and 7; right subtree 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 — each node's left subtree fully printed before the node itself, which is itself printed before its right subtree. $$\boxed{\text{inorder} = 1,3,4,6,7,8,10,13,14}$$

(b) find_max_leaf (10 marks)

1. Distinguish "largest value in the tree" from "largest value at a leaf." A node with at least one child is never a candidate, however large its own data — only nodes where both left and right are NULL qualify. The recursive answer for a subtree is therefore: if this node is itself a leaf, its own value is the answer; otherwise, recurse into whichever children exist and take the larger of their answers.
2. Write the function. An empty tree has no leaf at all; this is handled by returning a sentinel (here INT_MIN) that can never win a max comparison against a real leaf value found elsewhere in the recursion, and is flagged as an assumption since the question does not specify empty-tree behaviour for this function the way it does for inorder.

   #include <limits.h>
   
   int find_max_leaf(TreeNode *root)
   {
       int leftMax, rightMax;
   
       if (root == NULL)
           return INT_MIN;                      /* no leaf exists; see check note */
   
       if (root->left == NULL && root->right == NULL)
           return root->data;                   /* root itself is a leaf */
   
       leftMax  = find_max_leaf(root->left);
       rightMax = find_max_leaf(root->right);
       return (leftMax > rightMax) ? leftMax : rightMax;
   }

3. Trace it on the same example tree. The leaves are 1, 4, 7 and 13 — node 14 is not a leaf, since it has a left child (13), even though 14 > 13. The recursion returns $\max(1,4,7,13) = 13$, not 14. $$\boxed{\text{find\_max\_leaf} = 13\ \text{(not 14, which has a child)}}$$