@article { author = {Aghaieabiane, Niloofar and Koppelaar, Henk and Nasehpour, Peyman}, title = {An improved algorithm to reconstruct a binary tree from its inorder and postorder traversals}, journal = {Journal of Algorithms and Computation}, volume = {49}, number = {1}, pages = {93-113}, year = {2017}, publisher = {University of Tehran}, issn = {2476-2776}, eissn = {2476-2784}, doi = {10.22059/jac.2017.7987}, 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 = {Binary tree,Preorder traversal,Inorder traversal,Postorder traversal,time complexity,Space complexity}, url = {https://jac.ut.ac.ir/article_7987.html}, eprint = {https://jac.ut.ac.ir/article_7987_96afa0a5a26a75bad5082fc1b7e92603.pdf} }