BinarySearchTree

The tree built by inserting σ(1), σ(2), ... into an empty binary search tree.

WikipediaBinary search tree↗WikidataQ623818↗

BinarySearchTree(Permutation)

Domain: Combinatorial maps

Details

• Takes a `Permutation` and returns a `BinaryTree` — a typed map, so a wrong carrier is a type error rather than a wrong answer.
• The sylvester congruence: two permutations land on the same tree exactly when they agree on which of any pair is inserted first. See bst.ts for the parent-pointer encoding chosen for `binary_tree` and why.

Examples