Loading...
Please wait, while we are loading the content...
Similar Documents
Constructing a binary tree efficiently from its traversals (1998).
| Content Provider | CiteSeerX |
|---|---|
| Author | Traversals, Efficientlyfrom Its Mäkinen, Erkki Makinen, Erkki |
| Abstract | In this note we streamline an earlier algorithm for constructing a binary tree from its inorder and preorder traversals. The new algorithm is conceptually simpler than the earlier algorithms and its time complexity has a smaller constant factor. Keywords: Algorithms; Binary trees; Tree traversals. 1 Introduction Given the preorder and inorder traversals #or postorder and inorder traversals# of the nodes of a binary tree, the binary tree structure can be constructed. In the matter of fact, the construction is possible in linear time #1,4#. Recently, Xiang and Ushijima #5# have determined the constant factors of these algorithms bycounting the numbers of comparision operations needed. They found out that the linear coe#cientofM#akinen's algorithm #4# is 3 in the best case and 5 in the worst case, and that the corresponding coe#cients in the algorithm of Andersson and Carlsson #1# are 4 and 7. Moreover, Xiang and Ushijima presented a new algorithm with linear coe#cient 3 both in the be... |
| File Format | |
| Publisher Date | 1998-01-01 |
| Access Restriction | Open |
| Subject Keyword | Binary Tree Inorder Traversal Constant Factor New Algorithm Comparision Operation Preorder Traversal Introduction Given Corresponding Coe Cients Linear Time Linear Coe Cientofm Akinen Tree Traversal Linear Coe Cient Binary Tree Structure Time Complexity |
| Content Type | Text |
