Computing all subtree repeats in ordered trees

Michalis Christou*, Maxime Crochemore, Tomáš Flouri, Costas S. Iliopoulos, Jan Janoušek, Bořivoj Melichar, Solon P. Pissis

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review


We consider the problem of computing all subtree repeats in a given labeled ordered tree. We first transform the tree to a string representing its postfix notation, and then present an algorithm based on the bottom-up technique to solve it. The proposed algorithm consists of two phases: the preprocessing phase and the phase where all subtree repeats are computed. The linear time and space complexity of the proposed algorithm are important parts of its quality.

Original languageEnglish
Pages (from-to)958-962
Number of pages5
JournalInformation Processing Letters
Issue number24
Publication statusPublished - 31 Dec 2012
Externally publishedYes


  • Algorithms
  • Strings
  • Subtree repeats
  • Trees


Dive into the research topics of 'Computing all subtree repeats in ordered trees'. Together they form a unique fingerprint.

Cite this