Record number :
2469459
Title of article :
An improved algorithm to reconstruct a binary tree from its inorder and postorder traversals
Author/Authors :
Aghaieabiane, Niloofar Department of Engineering - School of Computer Science - New Jersey Institute of Technology - Newark - New Jersey, the USA , Koppelaar, Henk Faculty of Electrical Engineering - Mathematics and Computer Science - Delft University of Technology - Delft, The Netherlands , Nasehpour, Peyman Department of Engineering Science - Golpayegan University of Technology, Golpayegan
Pages :
21
From page :
93
To page :
113
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 O 􀀀 n2 . In this paper, we present 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 􀀀 n and 􀀀 n respectively, which we prove to be optimal. The InPos algorithm not only reconstructs the binary tree, but also it determines dierent 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 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
Journal title :
Astroparticle Physics
Serial Year :
2017
Link To Document :
بازگشت