BinaryTreeParentArray

The singular-inhabitant constructor for a binary tree as its in-order parent array: entry k is the k-th node's parent, 0 at the root.

BinaryTreeParentArray(list)The singular-inhabitant constructor for a binary tree as its in-order parent array: entry k is the k-th node's parent, 0 at the root.

Typed signatures

Type	Package	Applies
((list<integer>) -> binary_tree_parent_array) & ((binary_tree) -> binary_tree_parent_array)	combinatorics	always

Domain: Collections

Details

• Number the nodes in order. A node numbered below its parent is its left child, above it its right, so parentage alone fixes the tree: $2023$ is a root 2 with left child 1 and right child 3, and 4 to the right of 3.
• A binary search tree's values are its in-order numbers, which makes this what BinarySearchTreeParentArray builds. The same structure as a BinaryTree (BinaryTree(array), BinaryTreeParentArray(tree)), and through it a Dyck path.

Maps

Into and out of BinaryTreeParentArray, called as CombinatorialMap(x, "Name"). Properties are the laws we state and what FindStat records.

From BinaryTreeParentArray

• BinaryTreeBinaryTreeParentArray → BinaryTreeinverseThe binary tree an in-order parent array describes: a node below its parent goes left, above it right.

To BinaryTreeParentArray

• BinarySearchTreeParentArrayPermutation → BinaryTreeParentArrayThe binary search tree of σ as its parent array: entry v is the value v is inserted under, 0 for the root.
• BinaryTreeParentArrayBinaryTree → BinaryTreeParentArrayinverseA binary tree as its parent array: its nodes numbered in order, entry k the number of the k-th node's parent, 0 at the root.

Examples

Basic #

From a binary tree, its nodes numbered in order

live ↗

In$\operatorname{BinaryTreeParentArray}({\operatorname{BinaryTree}}(\bigl\lbrack\bigl\lbrack0, 0\bigr\rbrack, \bigl\lbrack0, \bigl\lbrack0, 0\bigr\rbrack\bigr\rbrack\bigr\rbrack))$Out${\operatorname{BinaryTreeParentArray}}([2, 0, 2, 3])$

About

Examples	1

See also: BinaryTreeParentArrays, BinaryTree