Two algorithms for constructing a binary tree from its traversals (Q1111397)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Two algorithms for constructing a binary tree from its traversals |
scientific article; zbMATH DE number 4076652
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Two algorithms for constructing a binary tree from its traversals |
scientific article; zbMATH DE number 4076652 |
Statements
Two algorithms for constructing a binary tree from its traversals (English)
0 references
1988
0 references
Given the inorder traversal of a binary tree, along with one of its preorder or postorder traversals, the original binary tree can be uniquely identified. We present two construction algorithms: one, which requires O(N) time, is time optimal but space inefficient, and the other requires O(N log N) time and O(N) space.
0 references
data structure
0 references
tree traversal
0 references
binary tree
0 references
