Creator |
|
|
|
Language |
|
Publisher |
|
|
Date |
|
Source Title |
|
Vol |
|
Issue |
|
First Page |
|
Last Page |
|
Publication Type |
|
Access Rights |
|
JaLC DOI |
|
Related DOI |
|
Related URI |
|
Relation |
|
Abstract |
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.show more
|