AFTD Auto-Formalizing Theoretical Domains

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

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
See it in the graphDiscuss this resultChallenge it