An improved algorithm to reconstruct a binary tree from its inorder and postorder traversals

Document Type: Research Paper

Authors

1 Department of Engineering, School of Computer Science, New Jersey Institute of Technology, Newark, New Jersey, the USA.

2 Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, Delft, The Netherlands.

3 Golpayegan University of Technology, Department of Engineering Science, Golpayegan, Iran.

Abstract

It is well-known that, given inorder traversal along with one of the preorder or postorder traversals of a binary tree, the tree can be determined uniquely. Several algorithms have been proposed to reconstruct a binary tree from its inorder and preorder traversals. There is one study to reconstruct a binary tree from its inorder and postorder traversals, and this algorithm takes running time of  $ \BigO{\emph{n}^2} $. In this paper, we present $ \proc{InPos} $ an improved algorithm to reconstruct a binary tree from its inorder and postorder traversals. The running time and space complexity of the algorithm are an order of $ \BigTheta{\emph{n}} $ and $ \BigTheta{\emph{n}} $ respectively, which we prove to be optimal.
 The $ \proc{InPos} $ algorithm not only reconstructs the binary tree, but also it determines different types of the nodes in a binary tree; nodes with two children, nodes with one child, and nodes with no child. At the end, the $ \proc{InPos} $ returns a matrix-based structure to represent the binary tree, and enabling  access to any structural information of the reconstructed tree in linear time with any given tree traversals.  

Keywords

Journal of Algorithms and Computation

Volume 49, Issue 1
June 2017
Pages 93-113

Files

Share

How to cite

Statistics