Two algorithms for constructing a binary tree from its traversals (Q1111397)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Two algorithms for constructing a binary tree from its traversals |
scientific article |
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
