Two Algorithms for Constructing a Binary Tree from its Traversals.
Journal
Inf. Process. Lett.
Journal Volume
28
Journal Issue
6
Pages
297-299
Date Issued
1988
Author(s)
Abstract
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. In this paper 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. © 1988.
Type
journal article