• Home
  • Browse
    • Current Issue
    • By Issue
    • By Author
    • By Subject
    • Author Index
    • Keyword Index
  • Journal Info
    • About Journal
    • Aims and Scope
    • Editorial Board
    • Editorial Staff
    • Publication Ethics
    • Indexing and Abstracting
    • Related Links
    • FAQ
    • Peer Review Process
    • News
  • Guide for Authors
  • Submit Manuscript
  • Reviewers
  • Contact Us
 
  • Login
  • Register
Home Articles List Article Information
  • Save Records
  • |
  • Printable Version
  • |
  • Recommend
  • |
  • How to cite Export to
    RIS EndNote BibTeX APA MLA Harvard Vancouver
  • |
  • Share Share
    CiteULike Mendeley Facebook Google LinkedIn Twitter
Journal of Algorithms and Computation
Articles in Press
Current Issue
Journal Archive
Volume Volume 51 (2019)
Volume Volume 50 (2018)
Volume Volume 49 (2017)
Issue Issue 2
December 2017
Issue Issue 1
June 2017
Volume Volume 48 (2016)
Volume Volume 47 (2016)
Volume Volume 46 (2015)
Volume Volume 45 (2014)
Volume Volume 44 (2013)
Volume Volume 43 (2009)
Volume Volume 42 (2008)
Volume Volume 41 (2007)
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

Article 9, Volume 49, Issue 1, June 2017, Page 93-113  XML PDF (442.04 K)
Document Type: Research Paper
Authors
Niloofar Aghaieabiane1; Henk Koppelaar2; Peyman Nasehpour email 3
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.  
Keywords
Binary tree; Preorder traversal; Inorder traversal; Postorder traversal; time complexity; Space complexity
Statistics
Article View: 139
PDF Download: 133
Home | Glossary | News | Aims and Scope | Sitemap
Top Top

This work is licensed under a Creative Commons Attribution 4.0 International License
Journal Management System. Designed by sinaweb.