We apologize for a recent technical issue with our email system, which temporarily affected account activations. Accounts have now been activated. Authors may proceed with paper submissions. PhDFocusTM
CFP last date
20 November 2024
Call for Paper
December Edition
IJCA solicits high quality original research papers for the upcoming December edition of the journal. The last date of research paper submission is 20 November 2024

Submit your paper
Know more
The week's pick
Responsive image
An Efficient Restoration Method for the Faint Dot Matrix Images

Ao Zhu Peng Cao
Random Articles
Reseach Article

Iterative Method for Recreating a Binary Tree from its Traversals

by Nitin Arora, Pradeep Kumar Kaushik, Satendra Kumar
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 57 - Number 11
Year of Publication: 2012
Authors: Nitin Arora, Pradeep Kumar Kaushik, Satendra Kumar
10.5120/9156-2056

Nitin Arora, Pradeep Kumar Kaushik, Satendra Kumar . Iterative Method for Recreating a Binary Tree from its Traversals. International Journal of Computer Applications. 57, 11 ( November 2012), 6-13. DOI=10.5120/9156-2056

@article{ 10.5120/9156-2056,
author = { Nitin Arora, Pradeep Kumar Kaushik, Satendra Kumar },
title = { Iterative Method for Recreating a Binary Tree from its Traversals },
journal = { International Journal of Computer Applications },
issue_date = { November 2012 },
volume = { 57 },
number = { 11 },
month = { November },
year = { 2012 },
issn = { 0975-8887 },
pages = { 6-13 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume57/number11/9156-2056/ },
doi = { 10.5120/9156-2056 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:00:08.193492+05:30
%A Nitin Arora
%A Pradeep Kumar Kaushik
%A Satendra Kumar
%T Iterative Method for Recreating a Binary Tree from its Traversals
%J International Journal of Computer Applications
%@ 0975-8887
%V 57
%N 11
%P 6-13
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Many reconstruction algorithms for binary tree have been discussed in this paper. A particular focus of this paper is on "A new Non-Recursive Algorithm for Reconstructing a Binary Tree from its Traversals". The computation time required for executing the reconstruction algorithm are O(N) and space complexity is O(NlogN) where N is the number of nodes in the binary tree. This algorithm works well for most of the input cases, but it has some drawbacks. There are some sequences of pre-order and in-order for which no legitimate tree can be constructed but the algorithm didn't take these cases into consideration and constructed a wrong tree for these cases. In this paper, we have proposed a solution to the problem in the previous algorithm and designed an algorithm which is the modified version of the previous algorithm for generating a correct binary tree. The new modified algorithm is implemented in C language and tested in GCC Compiler in Linux, for all types of input cases. The New modified algorithm works well for all types of input cases. We have calculated the best case time complexity of modified algorithm and show that a correct tree can be reported in O(N) time in best case and O(NlogN) space where N is the number of nodes in the tree. We have discussed some applications of the new modified algorithm in Huffman Coding, compiler design, text processing and searching algorithms.

References
  1. Vinu V Das, "Principles of Data Structures Using C and C++", New Age International Publishers, Reading, Mass. , 2005.
  2. M. Weiss, "Data Structures & Problem Solving Using Java", 2nd ed. , Addison Wesley, 2002.
  3. D. E. Knuth, "The Art of Computer Programming", Vol. 3 (2nd ed. ): Sorting and Searching, Addison Wesley, 1998.
  4. R. Sedgewick, "Algorithms in Java", 3d edition, Addison Wesley, 2003.
  5. D. E. Kunth, "The Art of Computer Programming", Vol. 1: Fundamental Algorithm, Addison-Wesley, Reading, Mass. , 1973.
  6. Mark Allen Weiss, "Data Structures and Algorithm Analysis in C", Vol. 3 (2nd ed. ), Addison-Wesley, 1997.
  7. Yedidyah Langsam, Moshe J. Augenstein, Aaron M. Tanenbaum: "Data Structures using C and C++", 2nd Ed. , Prentice-Hall India, July 2002.
  8. Sartaj Sahni: "Data Structures, Algorithms and Applications in JAVA", 2nd Ed. , University Press.
  9. A. Anderson and S. Carlsson: "Construction of a tree from its traversals in optimal time and space", Information Processing Letters, 34:21-25, 1990.
  10. N. Gabrani and P. Shankar: "A note on the reconstruction of a binary tree from its traversals", Information Processing Letters, 42:117-119, 1992.
  11. Vinu V Das, "A new Non-Recursive Algorithm for Reconstructing a Binary Tree from its Traversals", IEEE Comm. , pp. 261-263, 2010.
  12. H. A. Burgdorff, S. Jojodia, F. N. Springsteel, and Y. Zalcstein, "Alternative Methods for the Reconstruction of Tree from their Traversals", BIT, Vol. 27, No. 2, p. 134, 1987.
  13. G. H. Chen, M. S. Yu, and L. T. Liu: "Non-recursive Algorithms for Reconstructing a Binary Tree from its Traversals", IEEE Comm. , Vol. 88, pp. 490-492, 1988.
  14. C. C. Lee, D. T. Lee, C. K. Wong: "Generating Binary Trees of bounded height", Acta Inf. , 23, 529-544, 1986.
  15. Seymour Lipschutz: "Theory and problem of Data Structures", International Edition, McGRAW-HILL, 1986.
  16. Glenn W. Rowe: "Introduction to Data Structure and Algorithms with C++", PHI, ISBN: 81-203-1277-5.
  17. Robert Sedgewick: "Algorithms in C++", Ed. 3rd, 2001, ISBN: 81-7808-249-7.
  18. C. P. Kruskal: "Searching, merging, and sorting in parallel computation", IEEE Transactions on Computers, 32:924-946, 1983.
  19. Lindstrom, G. Scanning: "List structures without stacks or tag bits". Inform. Proc. Letters 2, 1973, pp. 47-51.
  20. Arora N. , Tamta V. and Kumar S: "Modified Non-Recursive Algorithm for Reconstructing a Binary Tree from its Traversals", IJCA, volume 43-No. 10, April 2012.
Index Terms

Computer Science
Information Sciences

Keywords

Non-recursive tree traversals binary tree

Powered by PhDFocusTM