PathLength

BinaryTree: The sum of the depths of the nodes, the root's being 0: the internal path length. OrderedTree: The sum of the depths of the vertices, the root's being 0.

✓ checked against that system · ! checked, with disagreements (hover a chip)FindStatSt000398via BinaryTree✓↗St000400via OrderedTree✓↗

PathLength(tree)BinaryTree: The sum of the depths of the nodes, the root's being 0: the internal path length. OrderedTree: The sum of the depths of the vertices, the root's being 0.

Typed signatures

Type	Package	Applies
(binary_tree | ordered_tree) -> number	combinatorics	always

Domain: Tree statistics

Details

• Defined over BinaryTree as an expression in _x, evaluated by compute-engine — the definition IS the implementation.
• Takes a BinaryTree and nothing else — it reads values against their positions, or walks the orbits, so it needs the bijection. Applying it to a bare list is a type error, not a wrong answer.
• Defined over OrderedTree as an expression in _x, evaluated by compute-engine — the definition IS the implementation.
• Takes a OrderedTree and nothing else — it reads values against their positions, or walks the orbits, so it needs the bijection. Applying it to a bare list is a type error, not a wrong answer.
• Each vertex below a child sits one deeper than in the child's own tree, so the child contributes its vertex count plus its own path length.

Definition

Epsil, as the implementation runs it.

on BinaryTree, over _x

Apply(
       Function(0 if t in Integers else level + self(self, t[1], level + 1) +
                                        self(self, t[2], level + 1), self, t, level),
       Function(0 if t in Integers else level + self(self, t[1], level + 1) +
                                        self(self, t[2], level + 1), self, t, level),
       _x,
       0,
     )

on OrderedTree, over _x

Apply(
       Function(
                 [1, 0] if Length(t) == 0 else Apply(
                                                      (r: collection) => [1 +
                                                                          r[1], r[2]],
                                                      Fold(
                                                            Function(
                                                                      [a[1] +
                                                                       b[1], a[2] +
                                                                         b[1] +
                                                                         b[2]],
                                                                      a,
                                                                      b,
                                                                    ),
                                                            [0, 0],
                                                            Map(Function(
                                                                          self(self, c),
                                                                          c,
                                                                        ), t),
                                                          ),
                                                    ),
                 self,
                 t,
               ),
       Function(
                 [1, 0] if Length(t) == 0 else Apply(
                                                      (r: collection) => [1 +
                                                                          r[1], r[2]],
                                                      Fold(
                                                            Function(
                                                                      [a[1] +
                                                                       b[1], a[2] +
                                                                         b[1] +
                                                                         b[2]],
                                                                      a,
                                                                      b,
                                                                    ),
                                                            [0, 0],
                                                            Map(Function(
                                                                          self(self, c),
                                                                          c,
                                                                        ), t),
                                                          ),
                                                    ),
                 self,
                 t,
               ),
       _x,
     )[2]

Examples

Basic #

the binary tree $[[.,.],[[.,.],.]]$

live ↗

In$\mathrm{PathLength}({\operatorname{BinaryTree}}(\bigl\lbrack\bigl\lbrack0, 0\bigr\rbrack, \bigl\lbrack\bigl\lbrack0, 0\bigr\rbrack, 0\bigr\rbrack\bigr\rbrack))$Out$4$

the ordered tree $[[],[[]],[]]$

live ↗

In$\mathrm{PathLength}({\operatorname{OrderedTree}}(\bigl\lbrack\bigl\lbrack\bigr\rbrack, \bigl\lbrack\bigl\lbrack\bigr\rbrack\bigr\rbrack, \bigl\lbrack\bigr\rbrack\bigr\rbrack))$Out$5$

Properties #

FindStat's value for [.,.]

live ↗

In$\mathrm{CombinatorialStat}({\operatorname{BinaryTree}}(\bigl\lbrack0, 0\bigr\rbrack), \text{PathLength})$Out$0$

Known value · FindStat St000398

FindStat's value for [.,[.,.]]

live ↗

In$\mathrm{CombinatorialStat}({\operatorname{BinaryTree}}(\bigl\lbrack0, \bigl\lbrack0, 0\bigr\rbrack\bigr\rbrack), \text{PathLength})$Out$1$

Known value · FindStat St000398

FindStat's value for [[.,.],.]

live ↗

In$\mathrm{CombinatorialStat}({\operatorname{BinaryTree}}(\bigl\lbrack\bigl\lbrack0, 0\bigr\rbrack, 0\bigr\rbrack), \text{PathLength})$Out$1$

Known value · FindStat St000398

FindStat's value for [[]]

live ↗

In$\mathrm{CombinatorialStat}({\operatorname{OrderedTree}}(\bigl\lbrack\bigl\lbrack\bigr\rbrack\bigr\rbrack), \text{PathLength})$Out$1$

Known value · FindStat St000400

FindStat's value for [[[]]]

live ↗

In$\mathrm{CombinatorialStat}({\operatorname{OrderedTree}}(\bigl\lbrack\bigl\lbrack\bigl\lbrack\bigr\rbrack\bigr\rbrack\bigr\rbrack), \text{PathLength})$Out$3$

Known value · FindStat St000400

FindStat's value for [[],[]]

live ↗

In$\mathrm{CombinatorialStat}({\operatorname{OrderedTree}}(\bigl\lbrack\bigl\lbrack\bigr\rbrack, \bigl\lbrack\bigr\rbrack\bigr\rbrack), \text{PathLength})$Out$2$

Known value · FindStat St000400

About

Examples	8
Crosswalk	FindStat ×2