×

A note on the reconstruction of a binary tree from its traversals. (English) Zbl 0780.68057

Summary: We present a linear-time sequential algorithm for the construction of a binary tree, given its preorder and inorder traversals. The algorithm leads to an optimal \(O(\log n)\) time parallel algorithm on the EREW PRAM model, where \(n\) is the number of nodes in the tree.

MSC:

68Q25 Analysis of algorithms and problem complexity
68W15 Distributed algorithms
68P05 Data structures
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Andersson, A.; Carlsson, S., Construction of a tree from its traversals in optimal time and space, Inform. Process. Lett., 34, 1, 21-25 (1990) · Zbl 0695.68014
[2] Berkman, O.; Breslauer, D.; Galil, Z.; Schieber, B.; Vishkin, U., Highly parallelizable problems, Proc. 21st Ann. ACM Symp. on Theory of Computing, 309-319 (1989)
[3] Burgdorff, H. A.; Jajodia, S.; Springsteel, F. N.; Zalcstein, Y., Alternative methods for reconstruction of trees from their traversals, BIT, 27, 134-140 (1987)
[4] Chen, G.-H.; Yu, M. S.; Liu, L. T., Two algorithms for constructing a binary trees from its traversals, Inform. Process. Lett., 28, 297-299 (1988) · Zbl 0658.68084
[5] Hikita, T., Listing and counting subtrees of equal size of a binary tree, Inform. Process. Lett., 17, 225-229 (1983) · Zbl 0521.68072
[6] Kwon-Kim, S., Optimal parallel algorithms for sorted intervals, Proc. Ann. Allerton Conf. (1989)
[7] Ladner, R. E.; Fischer, M. J., Parallel prefix computation, J. ACM, 27, 831-838 (1980) · Zbl 0445.68066
[8] Olariu, S.; Overstreet, C.; Wen, Z., An optimal parallel algorithm to reconstruct a binary tree from its traversals, (Proc. Internat. Conf. on Computing and Information, 497 (1991), Springer: Springer New York), 484-495, Lecture Notes in Computer Science
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.