Aghaieabiane, N., Koppelaar, H., Nasehpour, P. (2017). An improved algorithm to reconstruct a binary tree from its inorder and postorder traversals. Journal of Algorithms and Computation, 49(1), 93-113.
Niloofar Aghaieabiane; Henk Koppelaar; Peyman Nasehpour. "An improved algorithm to reconstruct a binary tree from its inorder and postorder traversals". Journal of Algorithms and Computation, 49, 1, 2017, 93-113.
Aghaieabiane, N., Koppelaar, H., Nasehpour, P. (2017). 'An improved algorithm to reconstruct a binary tree from its inorder and postorder traversals', Journal of Algorithms and Computation, 49(1), pp. 93-113.
Aghaieabiane, N., Koppelaar, H., Nasehpour, P. An improved algorithm to reconstruct a binary tree from its inorder and postorder traversals. Journal of Algorithms and Computation, 2017; 49(1): 93-113.
An improved algorithm to reconstruct a binary tree from its inorder and postorder traversals
1Department of Engineering, School of Computer Science, New Jersey Institute of Technology, Newark, New Jersey, the USA.
2Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, Delft, The Netherlands.
3Golpayegan 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.
Top