Mini-project: Depth-first and breadth-first traversals

The goal of this mini-project is to spell out depth-first and breadth-first traversals by solving Exercise 07 in detail.

In the accompanying resource file, a type of binary tree is defined with a payload in the leaves:

type 'a binary_tree =
  | Leaf of 'a
  | Node of 'a binary_tree * 'a binary_tree;;

Four tree-traversing functions are defined that collect the payloads of any given tree into a list:

• traverse_foo_lifo : 'a binary_tree -> 'a list,
• traverse_foo_fifo : 'a binary_tree -> 'a list,
• traverse_bar_lifo : 'a binary_tree -> 'a list, and
• traverse_bar_fifo : 'a binary_tree -> 'a list.

Friendly hints about the extensional questions:

• “extensional” means that the questions are about the “what” of the traversal;
• draw the four binary trees based on the convention that in Node (x, y), x denotes the left subtree and y denotes the right subtree.

For example, the tree Node (Node (Leaf 3, Leaf 9), Leaf 5) is depicted as follows:

Friendly hints about the intensional questions:

• “intensional” means that the questions are about the “how” of the traversal;
• use the traced versions of traverse_foo_lifo, traverse_foo_fifo, traverse_bar_lifo, and traverse_bar_fifo provided in the resource file to visualize how the traversals are achieved.

Extensional question #1

Analyze the output of these tree-traversing functions on the four given trees t1, t2, t3, and t4. (In each case, one of the resulting lists stands out.)

Extensional question #2

Characterize the traversal that each of these functions implements, using the (self-explanatory) terms “depth first”, “breadth first”, “left to right”, and “right to left”. These terms are meant to be self-explanatory, though we used “depth first” and “breadth first” in Week 01 and “left to right” and “right to left” in the midterm project.

Extensional question #3

Test your characterization with 4 new telling examples (and explain why you find them telling).

Intensional question #1

Neither traverse_foo nor traverse_bar are structurally recursive (and so could not be written using fold_binary_tree). Why is that?

Hint:

• A function is structurally recursive when the type of its input is recursive (e.g., a list or a binary tree) and when it is defined with a base case and an induction step where the recursive call implements the induction hypothesis.
• Here, process is defined recursively and its input is a queue. Is the type of a queue recursive?

Intensional question #2 (time permitting)

1. Could you write a version of traverse_foo_lifo that is structurally recursive (and so could be written using fold_binary_tree)? If so, do it. Otherwise, say why.
2. Could you write a version of traverse_foo_fifo that is structurally recursive (and so could be written using fold_binary_tree)? If so, do it. Otherwise, say why.
3. Could you write a version of traverse_bar_lifo that is structurally recursive (and so could be written using fold_binary_tree)? If so, do it. Otherwise, say why.
4. Could you write a version of traverse_bar_fifo that is structurally recursive (and so could be written using fold_binary_tree)? If so, do it. Otherwise, say why.

Closing question (for the over-achievers)

Implement a functor (see Section Functors in the lecture notes of Week 13) that is parameterized by a queue in a way such that

• instantiating this functor with Lifo yields a module containing two functions, one equivalent to traverse_foo_lifo and the other to traverse_bar_lifo, and
• instantiating this functor with Fifo yields a module containing two functions, one equivalent to traverse_foo_fifo and the other to traverse_bar_fifo.

Resources

• The OCaml code for the present mini-project (latest version: 03 Nov 2022).

Version

Fixed two misspellings [21 Jan 2023]

Created [03 Nov 2022]