Listing and Counting Subtrees of a Tree
Frank Ruskey,
Department of Computer Science,
University of Victoria, Canada.
Abstract:
Given an ordered tree T, an ordering is defined on the set
of subtrees of T.
Algorithms are presented for listing all subtrees in that order,
and for determining the tree occupying a given position in the list.
The second algorithm runs in time proportional to the number of vertices
in the tree.
An explicit formula is given for the total number of subtrees summed over
all trees T.
Selected Citations:

Stephan G. Wagner,
Subset Counting in Trees,
Ars Combinatoria, 89 (2008) 127139.

Elmar Teufl and Stephan Wagner,
Enumeration Problems for Classes of SelfSimilar Graphs,
Journal of Combinatorial Theory, Series A.
114 (2007) 12541277.

Svante Janson,
Ideals In A Forest, OneWay Infinite Binary Trees And The
Contraction Method.
In ``Mathematics and Computer Science, II (Versailles, 2002),
Trends in Mathematics, Pages 393414.
Birkhauser, Basel, 2002.

Michel Habib, Raoul Medina, Lhouari Nourine, and George Steiner,
Efficient Algorithms on Distributive Lattices,
Discrete Applied Mathematics, 110 (2001) 169187.

V Kvasnicka, J Pospichal,
Simple Construction of Embedding Frequencies of Trees and Rooted Trees,
Journal of Chemical Information and Computer Sciences,
35 (1995) 121128.

Hosam M. Mahmoud,
Evolution of random search trees,
Wiley, New York, 1992, 324 pp., ISBN 0471532282.

E. Makinen,
A Survey on Binary Tree Codings,
The Computer Journal, 34 (1991) 438443.

Carl E. Langenhop and William E. Wright,
A model of the dynamic behavior of Btrees,
Acta Informatica, 27 (1989) 4159.

OEIS sequence
A007852.
Back to list of publications.