BinaryTrees
The binary trees with internal nodes, as nested lists: a leaf is , a node .
✓ checked against that system · ! checked, with disagreements (hover a chip)Wikipedia
Binary treeMathWorldBinaryTreeWikidataQ380172Encyclopedia of MathematicsBinary_treeOEISA000108✓A120588✓SageMathBinaryTrees(n)BinaryTrees(n)the binary trees with internal nodesTyped signatures
| Type | Package | Applies |
|---|---|---|
(integer<0..>) -> indexed_collection<binary_tree> | combinatorics | always |
Details
- Count is the Catalan number (see CatalanNumber)
- Listed by the size of the left subtree, then the left subtree's rank, then the right's. DyckPaths lists the same objects in another order:
DyckPath(tree)(up, left tree, down, right tree) is a bijection, so every Dyck path statistic answers on a tree, but the -th tree doesn't go to the -th path. - BinaryTreeParentArrays lists the same trees flat, in the same order.
Definition
Epsil, as the implementation runs it.
count(_n)
0 if 2 < 1 else 0 if _n < 0 else 0 if _n < 0 else _tables[1 * (Max(_n, 0) + 1) +
_n + 1]unrank(_n, _r)
Apply(
(kw: list<integer>) => Fold(
Function(Apply((bt: list<any>) => Apply((ba: integer) => ReplaceAt(
ReplaceAt(bs, 1, bt[1] - ba +
1),
bt[1] - ba +
2,
0 if ba == 0 else Fold(
Function(Apply((bc: list<any>) => Join(bc, [bt[bt[1] + 2 -
bi]]), bl), bl, bi),
[],
Range(1, ba, 1),
),
), kw[bj]), bs), bs, bj),
Join([0], Map(
Function(0, nz),
Range(1, 2 * _n + 1, 1),
)),
Range(2 * _n + 1, 1, -1),
)[2],
Apply(
(ufinal: list<integer>) => Map(
Function(ufinal[uv + 1], uv),
Range(1, 2 * _n + 1, 1),
),
Fold(
Function(Apply((ut: integer) => Apply((um: integer) => Apply(
(uk: integer) => Apply(
(ufound: list<integer>) => Apply((usz: integer) => Apply(
(urest: integer) => ReplaceAt(ReplaceAt(
ReplaceAt(ReplaceAt(
ReplaceAt(ReplaceAt(
ReplaceAt(ReplaceAt(us, 1, ut - 1 +
(1 if 1 < uk else 0) +
(1 if 0 < usz else 0)), ustep + 2, 2 if 0 < usz else 0),
2 * _n +
1 +
1 +
3 *
(ut - 1) +
1,
um - usz,
), 2 * _n +
1 +
1 +
3 *
(ut - 1) +
2, uk - 1),
2 * _n +
1 +
1 +
3 *
(ut - 1) +
3,
ufound[1] % urest,
), 2 * _n +
1 +
1 +
3 *
(ut +
(1 if 1 < uk else 0) -
1) +
1, usz - 1),
2 * _n +
1 +
1 +
3 *
(ut +
(1 if 1 < uk else 0) -
1) +
2,
2,
), 2 * _n +
1 +
1 +
3 *
(ut +
(1 if 1 < uk else 0) -
1) +
3, (ufound[1] -
ufound[1] % urest) /
urest),
0 if um - ufound[2] <
0 else _tables[(uk - 1) *
(Max(_n, 0) +
1) +
(um - ufound[2]) +
1],
), ufound[2]),
Fold(
Function(ua if ua[3] == 1 else [ua[1], ush, 1] if ua[1] <
(0 if ush < 0 else _tables[1 *
(Max(_n, 0) +
1) + ush + 1]) *
(0 if um - ush <
0 else _tables[(uk - 1) *
(Max(_n, 0) +
1) +
(um - ush) +
1]) else [ua[1] -
(0 if ush < 0 else _tables[1 *
(Max(_n, 0) +
1) + ush + 1]) *
(0 if um - ush <
0 else _tables[(uk - 1) *
(Max(_n, 0) +
1) +
(um - ush) +
1]), ush, 0], ua, ush),
[us[2 * _n +
1 +
1 +
3 *
(ut - 1) +
3], 0, 0],
Range(0, um, 1),
),
),
us[2 * _n +
1 +
1 +
3 *
(ut - 1) +
2],
), us[2 * _n +
1 +
1 +
3 *
(ut - 1) +
1]), us[1]), us, ustep),
Join(
[1, 2 if 0 < _n else 0],
Map(Function(0, pz), Range(1, 2 * _n, 1)),
[_n - 1, 2, _r],
Map(Function(0, pz), Range(1, 3 * (2 * _n + 4), 1)),
),
Range(1, 2 * _n, 1),
),
),
)rank(_n, _x)
Apply(
(kr: list<any>) => Apply((kw: list<integer>) => Fold(
Function(Apply((rt: integer) => Apply((rm: integer) => Apply(
(rk: integer) => Apply((rmult: integer) => Apply(
(rsub: list<integer>) => Apply((rsz: integer) => Apply(
(rfit: integer) => Apply(
(rbefore: integer) => ReplaceAt(ReplaceAt(
ReplaceAt(ReplaceAt(ReplaceAt(
ReplaceAt(ReplaceAt(ReplaceAt(rs, 1, rt - 1 +
(1 if 1 < rk else 0) +
(1 if 0 < rsz else 0)), 2, rs[2] +
rmult * rbefore), 2 +
3 *
(rt - 1) +
1, rm - rsz),
2 +
3 *
(rt - 1) +
2,
rk - 1,
), 2 +
3 *
(rt - 1) +
3, rmult), 2 +
3 *
(rt +
(1 if 1 < rk else 0) -
1) +
1, rsz - 1),
2 +
3 *
(rt +
(1 if 1 < rk else 0) -
1) +
2,
2,
), 2 +
3 *
(rt +
(1 if 1 < rk else 0) -
1) +
3, rmult * rfit),
Fold(Function(rc +
(0 if rq < 0 else _tables[1 *
(Max(_n, 0) +
1) + rq + 1]) *
(0 if rm - rq <
0 else _tables[(rk - 1) *
(Max(_n, 0) +
1) +
(rm - rq) +
1]), rc, rq), 0, Range(0, rsz - 1, 1)),
),
0 if rm - rsz <
0 else _tables[(rk - 1) *
(Max(_n, 0) +
1) +
(rm - rsz) +
1],
), rsub[2]),
Fold(
Function(rb if rb[1] == 0 else [rb[1] + kw[rj] -
1, rb[2] +
(1 if kw[rj] == 2 else 0)], rb, rj),
[1, 0],
Range(rstep + 1, Length(kw), 1),
),
), rs[2 +
3 *
(rt - 1) +
3]),
rs[2 +
3 *
(rt - 1) +
2],
), rs[2 +
3 *
(rt - 1) +
1]), rs[1]), rs, rstep),
Join(
[
1,
0,
_n - 1,
2,
1,
],
Map(
Function(0, pz),
Range(
1,
3 *
(2 * _n +
4),
1,
),
),
),
Range(1, 2 * _n, 1),
)[2], Take(
Drop(
kr,
3,
),
2 * _n + 1,
)),
Fold(
Function(Apply((ft: list<any>) => ft if ft[1] == 0 else ReplaceAt(
ReplaceAt(
ReplaceAt(
ReplaceAt(ft, 1, ft[1] - 1),
2,
ft[2] + 1,
),
3,
ft[3] if ft[2 * _n +
1 + 3 + ft[1]] ==
0 else 1,
),
ft[2] + 4,
0,
) if ft[2 * _n +
1 + 3 + ft[1]] in
Integers else Fold(
Function(ReplaceAt(
fa,
2 * _n +
1 +
3 +
(ft[1] + fi -
1),
ft[2 * _n +
1 + 3 + ft[1]][2 + 1 -
fi],
), fa, fi),
ReplaceAt(
ReplaceAt(ReplaceAt(ReplaceAt(ft, 1, ft[1] + 2 -
1), 2, ft[2] + 1), 3, ft[3]),
ft[2] + 4,
2,
),
Range(1, 2, 1),
) if Length(ft[2 * _n +
1 + 3 + ft[1]]) ==
2 else ReplaceAt(
ReplaceAt(ReplaceAt(ReplaceAt(ft, 1, ft[1] - 1), 2, ft[2] + 1), 3, 1),
ft[2] + 4,
2,
), fs), fs, fj),
Join(
[1, 0, 0],
Map(Function(0, nz), Range(1, 2 * _n + 1, 1)),
[_x],
Map(Function(0, nz), Range(1, 2 * (2 * _n + 1), 1)),
),
Range(1, 2 * _n + 1, 1),
),
)valid(_n, _x)
False if 2 < 1 else Apply(
(kr: list<any>) => kr[1] == 0 &&
kr[2] == 2 * _n + 1 && kr[3] == 0,
Fold(
Function(Apply((ft: list<any>) => ft if ft[1] ==
0 else ReplaceAt(ReplaceAt(
ReplaceAt(
ReplaceAt(ft, 1, ft[1] - 1),
2,
ft[2] + 1,
),
3,
ft[3] if ft[2 * _n +
1 + 3 + ft[1]] ==
0 else 1,
), ft[2] + 4, 0) if ft[2 * _n +
1 + 3 + ft[1]] in
Integers else Fold(
Function(ReplaceAt(fa, 2 * _n +
1 +
3 +
(ft[1] + fi -
1), ft[2 * _n +
1 + 3 + ft[1]][2 + 1 -
fi]), fa, fi),
ReplaceAt(
ReplaceAt(ReplaceAt(ReplaceAt(ft, 1, ft[1] + 2 -
1), 2, ft[2] + 1), 3, ft[3]),
ft[2] + 4,
2,
),
Range(1, 2, 1),
) if Length(ft[2 * _n +
1 + 3 + ft[1]]) ==
2 else ReplaceAt(
ReplaceAt(ReplaceAt(ReplaceAt(ft, 1, ft[1] - 1), 2, ft[2] + 1), 3, 1),
ft[2] + 4,
2,
), fs), fs, fj),
Join(
[1, 0, 0],
Map(
Function(0, nz),
Range(1, 2 * _n + 1, 1),
),
[_x],
Map(
Function(0, nz),
Range(1, 2 * (2 * _n + 1), 1),
),
),
Range(1, 2 * _n + 1, 1),
),
)tables(_n)
Fold(Function(Apply(
(fa: list<integer>) => Fold(
Function(Apply((fc: list<integer>) => ReplaceAt(
fb,
fj *
(Max(_n, 0) +
1) + fm + 1,
Fold(Function(fs +
fc[1 *
(Max(_n, 0) +
1) + fi + 1] *
fc[(fj - 1) *
(Max(_n, 0) +
1) +
(fm - fi) +
1], fs, fi), 0, Range(0, fm, 1)),
), fb), fb, fj),
fa,
Range(2, 2, 1),
),
ReplaceAt(
ft,
1 * (Max(_n, 0) + 1) + fm + 1,
1 if fm == 0 else ft[2 * (Max(_n, 0) + 1) +
(fm - 1) + 1],
),
), ft, fm), ReplaceAt(Map(
Function(0, pz),
Range(
1,
(Max(2, 1) + 1) * (Max(
_n,
0,
) + 1),
1,
),
), 1, 1), Range(0, Max(_n, 0), 1))Statistics
On BinaryTree, called as CombinatorialStat(x, "Name").
- BinaryNodesSt000196The number of nodes with two children.
- BoundaryNodesSt000203The number of nodes on the left spine or the right spine, the root counted once.
- CollessIndexSt001376The sum, over the nodes, of how much the node counts of the two subtrees differ.
- DistinctSubtreesSt001554The number of different nonempty subtrees.
- ExternalPathLengthSt000399The sum of the lengths of the paths from the root to the empty subtrees.
- ForkRightRightLeftPatternCountSt000132The number of nodes with two children whose right child's right child has a left child.
- HeightSt000050The height: the most nodes on a path from the root, 0 for the empty tree.
- HookNumberSt000568The number of hooks in the decomposition of the tree into hooks: a node with the chains of left children and of right children below it, the subtrees hanging off those chains decomposed in turn.
- LeavesSt000201The number of nodes with no children.
- LeftSpineSt000061The number of nodes on the left spine: the root and its chain of left children.
- LeftSubtreeSizeSt000051The number of nodes in the left subtree of the root.
- LinearExtensionCountSt000045The number of linear extensions of the tree as a poset: n! over the tree factorial.
- MaximalLeftBranchesSt000919The number of maximal paths of left edges.
- NonBoundaryNodesSt000204The number of nodes on neither the left spine nor the right spine.
- NonRootBinaryNodesSt000252The number of nodes other than the root with two children.
- ParenthesisCodeValueSt000198The value, read in binary, of the tree's parenthesis word: each node is ( left ) right, with ( as 1 and ) as 0.
- PathLengthSt000398The sum of the depths of the nodes, the root's being 0: the internal path length.
- PitchforksSt000409The number of nodes whose subtree has exactly two nodes.
- ProtectionNumberSt000701The edges from the root to the nearest leaf, a binary tree's empty subtree counting as a leaf.
- RightChildCountSt000083The number of nodes with a right child.
- RightForkRightLeftPatternCountSt000130The number of nodes whose right child has two children, the right one of which has a left child.
- RightLeftLeftLeftPathCountSt000131The number of nodes from which taking the right, then the left, then the left, then the left child stays inside the tree.
- RightLeftLeftPathCountSt000125The number of nodes from which taking the right, then the left, then the left child stays inside the tree.
- RightRightLeftLeftPathCountSt000129The number of nodes from which taking the right, then the right, then the left, then the left child stays inside the tree.
- RightRightLeftPathCountSt000122The number of nodes from which taking the right, then the right, then the left child stays inside the tree.
- RightRightLeftRightPathCountSt000128The number of nodes from which taking the right, then the right, then the left, then the right child stays inside the tree.
- RightRightPathCountSt000118The number of nodes from which taking the right, then the right child stays inside the tree.
- RightRightRightLeftPathCountSt000127The number of nodes from which taking the right, then the right, then the right, then the left child stays inside the tree.
- RightRightRightPathCountSt000121The number of nodes from which taking the right, then the right, then the right child stays inside the tree.
- RightRightRightRightPathCountSt000126The number of nodes from which taking the right, then the right, then the right, then the right child stays inside the tree.
- RightSubtreeSizeSumSt000161The sum, over the nodes, of the number of nodes in the right subtree.
- StrahlerNumberSt000396The Horton-Strahler number (register function): 0 for the empty tree, else the larger child's, plus one if the children tie.
- SwapEquivalentTreeCountSt000412The number of binary trees that become this one when the children at any nodes are swapped: each node with different subtrees (an only child counts as different from the empty one) doubles the count.
- SwapEquivalentTreeCountLogSt000414The binary logarithm of the number of binary trees with the same underlying rooted tree: the nodes whose two subtrees differ up to swaps.
- TreeFactorialSt000411The product, over the nodes, of the number of nodes at or below each.
- UnaryNodesSt000385The number of nodes with exactly one child.
- VertexHeightSumSt000569The sum, over the nodes, of the node's height (the most nodes on a path down).
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
Enumeration
Examples
1 more kept as data, checked against the oracles See also: DyckPaths, BinaryTreeParentArrays, CatalanNumber