On Constructing a Binary Tree from Its Traversals
Limin Xiang, Armin Lawi, Kazuo Ushijima · Kyushu University Institutional Repository (QIR) (Kyushu University) · 2000
Many algorithms have been presented for constructing a binary tree from its traversals. This problem can be solved by a sequential algorithm of linear time, such as E. Makinen's and A. Andersson and S. Carlsson's algorithms. If the number of comparison operations is used as a measure of time complexity, the linear coefficient of E. Makinen's is 3 in its best case and 5 in its worst case, and that of A. Andersson and S. Carlsson's is 4 in its best case and 7 in its worst case. In this article, we give a more efficient sequential algorithm for the problem, and the linear coefficient is 3 in any case.