Mini-project about indexing data structures, continued

The goal of this mini-project is to index binary trees.

Indexing binary trees

This mini-project builds on the mini-project about depth-first and breadth-first traversals. Its goal is to index a binary tree with a function of type 'a binary_tree -> int -> 'a option, where the polymorphic type binary_tree is defined as follows:

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

The tree traversals should be:

1. depth-first from left to right (provide two solutions: one which is structurally recursive, and one that isn’t)
2. depth-first from right to left (provide two solutions: one which is structurally recursive, and one that isn’t)
3. breadth-first from left to right
4. breadth-first from right to left

Version

Created [02 Apr 2022]