Height

The height of a Dyck path, a binary tree or an ordered tree, each counted as FindStat defines it.

✓ checked against that system · ! checked, with disagreements (hover a chip)FindStatSt000050via BinaryTree✓St000013via DyckPath✓St000166via OrderedTree✓

Height(path)The greatest height the Dyck path reaches.

Height(binaryTree)The most nodes on a path from the root, so a single node has height 1 and the empty tree 0 (St000050).

Height(orderedTree)The most edges on a path from the root, so a single vertex has height 0 (St000166).

Typed signatures

Type	Package	Applies
`(binary_tree \| dyck_path \| motzkin_path \| ordered_tree \| schroeder_path) -> number`	`combinatorics`	always

Domain: Path and tree statistics

Details

Defined over DyckPath as an expression in _x, evaluated by compute-engine — the definition IS the implementation.
Takes a DyckPath 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.
On a BinaryTree the height counts nodes: one node has height 1, the empty tree 0.
On an OrderedTree the height counts edges: one vertex has height 0.

Definition

Epsil, as the implementation runs it.

on DyckPath, over _x

0 if Length(_x) < 1 else Max(Map(Function(Sum(Map(
                                                   Function(2 * _x[k] - 1, k),
                                                   Range(1, i),
                                                 )), i), Range(1, Length(_x))))

on BinaryTree, over _x

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

on OrderedTree, over _x

Apply(
       Function(0 if Length(t) == 0 else 1 + Fold(
                                                   Function(Max(a, b), a, b),
                                                   0,
                                                   Map(Function(
                                                                 self(self, c),
                                                                 c,
                                                               ), t),
                                                 ), self, t),
       Function(0 if Length(t) == 0 else 1 + Fold(
                                                   Function(Max(a, b), a, b),
                                                   0,
                                                   Map(Function(
                                                                 self(self, c),
                                                                 c,
                                                               ), t),
                                                 ), self, t),
       _x,
     )