This file implements helper functions on binary trees. More
precisely, it implements complete binary trees, whose interior
nodes always have exactly two children (cf. the Wikipedia
page for the binary
tree). It basically reuses the tree
implementation and limits it to only build binary trees. In
a Typescript-like description :
typeBinaryTree<A> = BinaryNode<A> | BinaryLeaf<A> typeBinaryNode<A> = Node<A,List<A>> // The list is of length 2 typeBinaryLeaf<A> = Node<A,List<A>> // The list is nil
An important difference when comparing to trees is the fact that this
implementation prevents from building nodes with anything else than
0 or 2 children.
This implementation is obviously not efficient, and is mainly
here to show how to reuse the code from other implementations (here
lists and trees). A better implementation would
have its own internal representation without the superfluous lists.
This file implements helper functions on binary trees. More precisely, it implements complete binary trees, whose interior nodes always have exactly two children (cf. the Wikipedia page for the binary tree). It basically reuses the tree implementation and limits it to only build binary trees. In a Typescript-like description :
An important difference when comparing to trees is the fact that this implementation prevents from building nodes with anything else than 0 or 2 children.
This implementation is obviously not efficient, and is mainly here to show how to reuse the code from other implementations (here lists and trees). A better implementation would have its own internal representation without the superfluous lists.
Example
To create a binary tree :