Paper Info
Title
An Optimal Parallel Algorithm to Reconstruct a Binary Tree from its Traversals
Abstract
We consider the following problem. For a binary tree T=(V,E) where V={1, 2,...,n}, given its inorder traversal and either its preorder traversal or it postorder traversal, reconstruct the binary tree. We present a new parallel algorithm for this problem. Our algorithm requires O(n) space. The main idea of our algorithm is to reduce the reconstruction process to parallel merging. With the best results for parallel merging, our algorithm can be implemented in O(logn) time using O(n/logn) processors on the EREW PRAM, or in O(loglogn) time using O(n/log logn) processors on the CREW PRAM. Consequently, an ordered tree can be reconstructed from its preorder and postorder traversals. Our results improve the best previous results for this problem in literature either in cost or in the model of computation.
Year
DOI
Venue
1991
10.1007/3-540-54029-6_198
ICCI
Keywords
Field
DocType
optimal parallel algorithm,binary tree,model of computation,parallel algorithm
Combinatorics,Tree traversal,Treap,Computer science,Threaded binary tree,Parallel computing,K-ary tree,Optimal binary search tree,Binary search tree,Cartesian tree,Interval tree
Conference
ISBN
Citations 
PageRank 
3-540-54029-6
5
0.70
References 
Authors
8
3
Name
Order
Citations
PageRank
Stephan Olariu122719.83
C. Michael Overstreet220440.94
Zhaofang Wen3568.25