[FOM] Finite binary trees and ordinals
Dennis E. Hamilton
dennis.hamilton at acm.org
Wed Feb 14 16:28:11 EST 2007
There are schemes for the ordinal generation of the binary trees. I don't
know that it satisfies your conditions, but it seems to provide for a
successor process that can also be enumerated for each tree size:
Proskurowski, Andrzej. On the Generation of Binary Trees. Journal of the
ACM 27, 1 (January 1980), pp. 1-2. Available at
Of the citings on the ACM digital library page, two of them might also be
promising: the David Zerling paper and the Renzo Sprugnoli paper.
Here's the text of the abstract:
"A binary tree may be uniquelly represented by a *code* reflecting
traversal of the corresponding *extended binary tree* in a given *monotonic*
order. A general algorithm for constructing codes of all binary trees with
*n* vertices is presented. Different orders of traversal yield different
orderings of the generated trees. The algorithm is illustrated with an
example of the sequence of binary trees obtained from ballot sequences."
Ah yes, now I recognize why I remember it as providing Proskurowski
By "extended binary tree" is meant one in which all internal nodes have two
children. There are no sparse internal nodes - only binary nodes (n of
them) and 0-ary leaves (n+1 of them).
The ordinal generation is of successive extended binary trees with the same
number of internal nodes. From each one of these, one can generate the ones
that have fewer leaves (but that do not change the status of any internal
node), if desired.
From: fom-bounces at cs.nyu.edu [mailto:fom-bounces at cs.nyu.edu] On Behalf Of
Sent: Wednesday, February 14, 2007 06:21
To: Foundations of Mathematics
Subject: [FOM] Finite binary trees and ordinals
The following seem 'natural' conditions to put on a well-ordering <
of finite binary trees:
1. If A is a proper part of B, then A < B.
2 If T(A) is a tree containing A as a part, and T(B) is a properly
formed tree that results from substituting B for A, then if A < B then
T(A) < T(B).
[ ... ]
But a natural question arises: What are the minimum equally
'natural' conditions that, if added to 1 and 2, ENSURE that the
well-ordering is of the order-type of the ordinals less than
As I say, that seems a natural question, but I can't find any
treatment of it. Any thoughts and/or pointers gratefully
Dr Peter Smith: Faculty of Philosophy, University of Cambridge
Gödel's Theorems: http://www.godelbook.net
LaTeX for Logicians: http://www.phil.cam.ac.uk/teaching_staff/Smith/LaTeX/
Idle musings: http://logicmatters.blogspot.com
FOM mailing list
FOM at cs.nyu.edu
More information about the FOM