Optional mini-project about computing the width of a binary tree

Let us revisit the canonical type of polymorphic binary trees with payloads in their leaves:

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

The width of a binary tree is the largest number of leaves and nodes at the same depth, and the goal here is to write an OCaml function that given a binary tree, computes its width.

Intuitively, the unit-test function is simple to write – for any given binary tree, draw it and measure its width:

let test_width_int candidate_width =
 (* test_width_int : (int binary_tree -> int) -> bool *)
  let b0 = (candidate_width (Leaf 1)
            = 1)
  and b1 = (candidate_width (Node (Leaf 1,
                                   Leaf 2))
            = 2)
  and b2 = (candidate_width (Node (Leaf 1,
                                   Node (Leaf 1,
                                         Leaf 2)))
            = 2)
  and b3 = (candidate_width (Node (Node (Leaf 1,
                                         Leaf 2),
                                   Leaf 2))
            = 2)
  and b4 = (candidate_width (Node (Node (Leaf 1,
                                         Leaf 2),
                                   Node (Leaf 3,
                                         Leaf 4)))
            = 4)
  and b5 = (candidate_width (Node (Node (Node (Leaf 1,
                                               Leaf 2),
                                         Leaf 2),
                                   Node (Node (Leaf 3,
                                               Leaf 4),
                                         Node (Leaf 5,
                                               Leaf 6))))
            = 6)
  and b6 = (candidate_width (Node (Node (Node (Node (Leaf 1,
                                                     Leaf 2),
                                               Leaf 2),
                                         Leaf 2),
                                   Node (Node (Leaf 3,
                                               Node (Leaf 3,
                                                     Leaf 4)),
                                         Node (Leaf 5,
                                               Leaf 6))))
            = 6)
  (* etc. *)
  in b0 && b1 && b2 && b3 && b4 && b5 && b6;;

For example,

• in the third and fourth test, the successive numbers of leaves and nodes at the successive depths are 1, 2, and 2, and therefore the width is 2;
• in the second-to-last test, the successive numbers of leaves and nodes at the successive depths are 1, 2, 4, and 6, and therefore the width is 6; and
• in the last test, the successive numbers of leaves and nodes at the successive depths are 1, 2, 4, 6, and 4, and therefore the width is 6.

Exercise 1

Expand the unit-test function above with your own tests, and justify them. (For example, does mirroring a tree preserve its width?)

Exercise 2

Specify width inductively, implement it with a structurally recursive OCaml function, and verify that it passes the unit tests.

Exercise 3

To make sure that your implementation is structurally recursive, express it using binary_tree_fold (and verify that it still passes the unit tests).

A witness implementation

Warning

This witness implementation uses arrays, which are properly introduced in Week 12.

For your convenience (and information), the accompanying resource file contains a simple imperative implementation of width to test the unit-test function with random trees. This simple implementation

1. computes the depth of the given tree,
2. allocates an array of 0’s with the corresponding length,
3. recursively re-traverses the given tree, incrementing the array at index i each time a leaf or a node is encountered at depth i, and
4. computes the largest index in the array, which is the result of the computation.

Exercise 4

By the way, why does this imperative implementation work?

Resources

• The OCaml code for the present lecture note (latest version: 03 Apr 2021).

Version

Created [03 Apr 2021]