BinarySearchTreeParentArray

The binary search tree of σ as its parent array: entry v is the value v is inserted under, 0 for the root.

BinarySearchTreeParentArray(Permutation)The binary search tree of σ as its parent array: entry v is the value v is inserted under, 0 for the root.

Typed signatures

Type	Package	Applies
(permutation) -> binary_tree_parent_array	combinatorics	always

Domain: Combinatorial maps

Details

• Takes a Permutation and returns a BinaryTreeParentArray — a typed map, so a wrong carrier is a type error rather than a wrong answer.
• A search tree's values are its in-order labels, so this is the tree's in-order parent array. See bst.ts for why a fold builds it this way.

Examples

Basic #

the one-line word $231$

live ↗

In$\mathrm{BinarySearchTreeParentArray}({\operatorname{Permutation}}([2, 3, 1]))$Out${\operatorname{BinaryTreeParentArray}}([2, 0, 2])$

About

Examples	1