Module binary_tree.api

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 :

type BinaryTree<A>   = BinaryNode<A> | BinaryLeaf<A>
type BinaryNode<A> = Node<A,List<A>> // The list is of length 2
type BinaryLeaf<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.

To create a binary tree :

import * as B from "./src/utils/binary_tree.api.js";

const aBTree = B.node(1, B.leaf(2), B.leaf(3));
anyToString(aBTree); // -> bnode(1, bleaf(2), bleaf(3))

Index

Functions