BinarySearchTree

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

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

Typed signatures

Type	Package	Applies
`(permutation) -> binary_tree`	`combinatorics`	always

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.
Defined as a COMPOSITION, applied right to left: BinaryTree after BinarySearchTreeParentArray. Each step goes through its own declared head, so every intermediate value is a properly constructed carrier.
The sylvester congruence: two permutations land on the same tree exactly when they agree on which of any pair is inserted first. Built as its parent array (BinarySearchTreeParentArray), then read as a tree.

Examples

Basic #

the one-line word $231$

\mathrm{BinarySearchTree}({\operatorname{Permutation}}([2, 3, 1]))

Out

{\operatorname{BinaryTree}}(\bigl\lbrack\bigl\lbrack0, 0\bigr\rbrack, \bigl\lbrack0, 0\bigr\rbrack\bigr\rbrack)

About

Examples	1
Crosswalk	Wikipedia Wikidata FindStat