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.

The postscript file.
The pdf file.
For further results on this problem see
- Koda and Ruskey, A Gray Code for the Ideals of a Forest Poset, Journal of Algorithms, 15 (1993) 324-340.
- Klazar,

Selected Citations:

Stephan G. Wagner, Subset Counting in Trees, Ars Combinatoria, 89 (2008) 127-139.
Elmar Teufl and Stephan Wagner, Enumeration Problems for Classes of Self-Similar Graphs, Journal of Combinatorial Theory, Series A. 114 (2007) 1254-1277.
Svante Janson, Ideals In A Forest, One-Way Infinite Binary Trees And The Contraction Method. In ``Mathematics and Computer Science, II (Versailles, 2002), Trends in Mathematics, Pages 393-414. Birkhauser, Basel, 2002.
Michel Habib, Raoul Medina, Lhouari Nourine, and George Steiner, Efficient Algorithms on Distributive Lattices, Discrete Applied Mathematics, 110 (2001) 169-187.
V Kvasnicka, J Pospichal, Simple Construction of Embedding Frequencies of Trees and Rooted Trees, Journal of Chemical Information and Computer Sciences, 35 (1995) 121-128.
Hosam M. Mahmoud, Evolution of random search trees, Wiley, New York, 1992, 324 pp., ISBN 0-471-53228-2.
E. Makinen, A Survey on Binary Tree Codings, The Computer Journal, 34 (1991) 438-443.
Carl E. Langenhop and William E. Wright, A model of the dynamic behavior of B-trees, Acta Informatica, 27 (1989) 41-59.
OEIS sequence A007852.

Back to list of publications.