A top down algorithm for constrained tree inclusion

Given two ordered labeled trees P and T, the constrained tree inclusion problem is to determine whether it is possible to obtain P from T   through a sequence of deleting degree-one or degree-two nodes. Valiente proposed a bottom up algorithm which solves the problem in O(nPnT)O(nPnT) time and O(nPnT)O(nPnT) space, where nPnP and nTnT are the numbers of the nodes in P and T   respectively. In this paper we present a top down matching algorithm which solves the problem in O(nPnT)O(nPnT) time but uses only O(nP+nT)O(nP+nT) space.