notatio

BinaryTree ​

The singular-inhabitant constructor for a binary tree, nested: a leaf is 0, a node [left, right].

WikipediaBinary treeMathWorldBinaryTreeWikidataQ380172Encyclopedia of MathematicsBinary_treeOEISA000108via BinaryTreesFindStatMp00034via DyckPathMp00049via OrderedTreeSageMathBinaryTrees(n)via BinaryTrees
BinaryTree(tree)The singular-inhabitant constructor for a binary tree, nested: a leaf is 0, a node [left, right].
Typed signatures
TypePackageApplies
((integer | list<any>) -> binary_tree) & ((binary_tree_parent_array) -> binary_tree) & ((ordered_tree) -> binary_tree) & ((dyck_path) -> binary_tree)combinatoricsalways

Domain: Collections·Drawn as Graphics

Details
  • BinaryTree([[0, 0], 0]) is a root whose left child is a single node. The empty tree is BinaryTree(0).
  • The same structure as a Dyck path, U φ(L) D φ(R) (DyckPath(tree), FindStat's Mp00012), and as its in-order parent array (BinaryTreeParentArray(tree)); BinaryTree of either converts back. Both are bijections, so every Dyck path statistic answers on a tree. The parent arrays also keep BinaryTrees' order.
  • BinaryTree of an ordered tree is FindStat's Mp00049 (a vertex's left brother becomes its left child, its last child the right one, and the root goes). RightBranchBinaryTree is the same with left and right exchanged (Mp00050).

Statistics

On BinaryTree, called as CombinatorialStat(x, "Name").

Maps

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

From BinaryTree

  • 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.
  • DyckPathBinaryTree → DyckPathinverseBijectionGraded mapMp00012A binary tree [L, R] as the Dyck path U φ(L) D φ(R).
  • LeftBorderSymmetryBinaryTree → BinaryTreeinvolutionBijectionGraded mapInvolutionMp00018Reverse the order of the right subtrees hanging off the left border, applying the same symmetry inside each.
  • LeftRotationBinaryTree → BinaryTreebijectioninverseBijectionGraded mapMp00009Rotate the root to the left: the right child becomes the root, the root its left child.
  • MirrorBinaryTree → BinaryTreeinvolutionBijectionGraded mapInvolutionMp00016The left-right symmetry of a binary tree: every node's two subtrees swapped.
  • OrderedTreeBinaryTree → OrderedTreeinverseBijectionGraded mapMp00010A binary tree as an ordered tree with one more vertex: a left child becomes its parent's left brother, a right child its parent's last child.
  • RightBranchOrderedTreeBinaryTree → OrderedTreeinverseBijectionGraded mapMp00015A binary tree as an ordered tree with one more vertex: a right child becomes its parent's right brother, a left child its parent's first child.
  • RightRotationBinaryTree → BinaryTreebijectioninverseBijectionGraded mapMp00019Rotate the root to the right: the left child becomes the root, the root its right child.
  • TamariDyckPathBinaryTree → DyckPathbijectioninverseBijectionGraded mapMp00020The Dyck path T(L) U T(R) D of a tree with subtrees L and R: the bijection compatible with the Tamari order.

To BinaryTree

  • BinarySearchTreePermutation → BinaryTreesurjectionSurjectionGraded mapMp00072The tree built by inserting σ(1), σ(2), ... into an empty binary search tree.
  • BinaryTreeBinaryTreeParentArray → BinaryTreeinverseThe binary tree an in-order parent array describes: a node below its parent goes left, above it right.
  • BinaryTreeOrderedTree → BinaryTreeinverseBijectionGraded mapMp00049An ordered tree as a binary tree with one fewer node: a vertex's left brother becomes its left child, its last child its right child, and the root goes.
  • BinaryTreeDyckPath → BinaryTreeinverseBijectionGraded mapMp00034A Dyck path U A D B, cut at its first return, as the binary tree [φ⁻¹(A), φ⁻¹(B)].
  • RightBranchBinaryTreeOrderedTree → BinaryTreeinverseBijectionGraded mapMp00050An ordered tree as a binary tree with one fewer node: a vertex's right brother becomes its right child, its first child its left child, and the root goes.
  • TamariBinaryTreeDyckPath → BinaryTreebijectionBijectionGraded mapMp00029A path D = L U R D as the binary tree whose left and right subtrees are those of L and R: the bijection compatible with the Tamari order.
9 more in FindStat, not implemented here
  • Mp00008BinaryTree → OrderedTreeInjectionGraded mapto complete tree
  • Mp00011BinaryTree → LabeledGraphGraded mapto graph
  • Mp00013BinaryTree → PosetsGraded mapto poset
  • Mp00014BinaryTree → PermutationInjectionGraded mapto 132-avoiding permutation
  • Mp00017BinaryTree → PermutationInjectionGraded mapto 312-avoiding permutation
  • Mp00061Permutation → BinaryTreeSurjectionGraded mapto increasing tree
  • Mp00139OrderedTree → BinaryTreeBijectionGraded mapZeilberger's Strahler bijection
  • Mp00140DyckPath → BinaryTreeBijectionGraded maplogarithmic height to pruning number
  • Mp00141BinaryTree → DyckPathBijectionGraded mappruning number to logarithmic height

Examples

Basic #

From a Dyck path, cut at its first return

live ↗
InBinaryTree⁡(DyckPath⁡([1,1,0,0,1,0])){\operatorname{BinaryTree}}({\operatorname{DyckPath}}([1, 1, 0, 0, 1, 0]))OutBinaryTree⁡([[0,0],[0,0]]){\operatorname{BinaryTree}}(\bigl\lbrack\bigl\lbrack0, 0\bigr\rbrack, \bigl\lbrack0, 0\bigr\rbrack\bigr\rbrack)

From its in-order parent array

live ↗
InBinaryTree⁡(BinaryTreeParentArray⁡([2,0,2,3])){\operatorname{BinaryTree}}({\operatorname{BinaryTreeParentArray}}([2, 0, 2, 3]))OutBinaryTree⁡([[0,0],[0,[0,0]]]){\operatorname{BinaryTree}}(\bigl\lbrack\bigl\lbrack0, 0\bigr\rbrack, \bigl\lbrack0, \bigl\lbrack0, 0\bigr\rbrack\bigr\rbrack\bigr\rbrack)
About
Examples2
CrosswalkWikipediaMathWorldWikidataEncyclopedia of MathematicsOEISFindStat ×2SageMath

See also: BinaryTrees, BinaryTreeParentArray, DyckPath