# 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