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 :