Thumbnail
Access Restriction
Subscribed

Author Chen, G.H. ♦ Yu, M.S. ♦ Liu, L.T.
Source IEEE Xplore Digital Library
Content type Text
Publisher Institute of Electrical and Electronics Engineers, Inc. (IEEE)
File Format PDF
Copyright Year ©1988
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Binary trees ♦ Reconstruction algorithms ♦ Computer science ♦ Acceleration
Abstract The authors propose two nonrecursive algorithms for reconstructing the original binary tree from its inorder and preorder traversals. The proposed algorithms proceed in two stages: the first stage establishes the i-p sequence while the second stage reconstructs the binary tree from the i-p sequence. One algorithm, which requires O(N) time, is time-optimal but space-inefficient, while the other requires O(N log N) time and O(N) space. If sorting and binary search are used, then the space required is optimal within a constant factor. If, instead, hashing is used, the computation time required is optimal within a constant factor. Simple modifications of the proposed algorithm can be used to reconstruct the original binary tree from its inorder and postorder traversals.<<ETX>>
Description Author affiliation: Dept. of Comput. Sci. & Inf. Eng., Nat. Taiwan Univ., Taipei, Taiwan (Chen, G.H.; Yu, M.S.; Liu, L.T.)
ISBN 0818608730
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research ♦ Reading
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1988-10-05
Publisher Place USA
Rights Holder Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Size (in Bytes) 162.59 kB
Page Count 3
Starting Page 490
Ending Page 492


Source: IEEE Xplore Digital Library