On Chen and Chen's new tree inclusion algorithm

Very recently, Chen and Chen [Y. Chen, Y. Chen, A new tree inclusion algorithm, Information Processing Letters 98 (2006) 253–262] gave a new algorithm for the tree inclusion problem, which requires O(|T|×min{depth(P),|leaves(P)|}) time and no extra space. In this Note, we show that there are flaws in their time-complexity analysis by presenting two counterexamples. We also give an example to show that the worst-case time complexity of their algorithm is non-polynomial. Consequently, the asymptotically most efficient algorithm for the tree inclusion problem is the former algorithm in [W. Chen, More efficient algorithm for ordered tree inclusion, Journal of Algorithms 26 (1998) 370–385].