Listing and Counting Subtrees of a Tree

Frank Ruskey, Department of Computer Science, University of Victoria, Canada.


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:
Back to list of publications.