comparison_tree_num_leaves
def
The number of leaves in a comparison decision tree is 1 for a leaf, and the sum of the leaf counts of its left and right subtrees for an internal branch.
Statement
def comparison_tree_num_leaves {n : ℕ} : ComparisonTree n → ℕ- Defined in
- arXiv:2610.18740, Section 5
- Verified
- 21 Oct 2026
- Axioms
- none listed
- Built on 1
- ComparisonTreeA binary comparison decision tree on n elements whose internal nodes perform pairwise comparisons and whose leaves return an element index.
- Used by 1
- comparison_tree_num_leaves_le_two_pow_depthFor any natural number n and any comparison decision tree T on n elements, the number of leaves of T is at most 2 raised to the depth of T.
Read back from the Lean
A definition of a function comparison_tree_num_leaves that takes an implicit natural number n and a tree of type ComparisonTree n, and returns a natural number by structural recursion: 1 if the tree is a leaf (leaf ans), and the sum of the recursive calls on the left and right subtrees if the tree is a branch (branch i j l r).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The number of leaves in a comparison decision tree. -/ def comparison_tree_num_leaves {n : ℕ} : ComparisonTree n → ℕ | .leaf _ => 1 | .branch _ _ l r => comparison_tree_num_leaves l + comparison_tree_num_leaves r