CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

Modified Non-Recursive Algorithm for Reconstructing a Binary Tree

by Nitin Arora, Vivek Kumar Tamta, Suresh Kumar
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 43 - Number 10
Year of Publication: 2012
Authors: Nitin Arora, Vivek Kumar Tamta, Suresh Kumar
10.5120/6141-8386

Nitin Arora, Vivek Kumar Tamta, Suresh Kumar . Modified Non-Recursive Algorithm for Reconstructing a Binary Tree. International Journal of Computer Applications. 43, 10 ( April 2012), 25-28. DOI=10.5120/6141-8386

@article{ 10.5120/6141-8386,
author = { Nitin Arora, Vivek Kumar Tamta, Suresh Kumar },
title = { Modified Non-Recursive Algorithm for Reconstructing a Binary Tree },
journal = { International Journal of Computer Applications },
issue_date = { April 2012 },
volume = { 43 },
number = { 10 },
month = { April },
year = { 2012 },
issn = { 0975-8887 },
pages = { 25-28 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume43/number10/6141-8386/ },
doi = { 10.5120/6141-8386 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:33:04.339747+05:30
%A Nitin Arora
%A Vivek Kumar Tamta
%A Suresh Kumar
%T Modified Non-Recursive Algorithm for Reconstructing a Binary Tree
%J International Journal of Computer Applications
%@ 0975-8887
%V 43
%N 10
%P 25-28
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Binary tree traversal refers to the process of visiting each node in a specified order. Given the inorder traversal of a binary tree, along with one of its preorder or postorder traversals, the original binary tree can be uniquely identified. Many recursive and non recursive method of construction of the tree from inorder and any of the postorder or preorder traversal have been proposed. In this paper one of the proposed algorithms has been examined. This algorithm computes the wrong tree for some input sequences. We show a particular situation in which the algorithm fails and a solution for this situation is proposed. The proposed a modified non-recursive algorithm for reconstructing a binary tree which generates the correct tree otherwise an error has been reported.

References
  1. Vinu V Das, "A new Non-Recursive Algorithm for Reconstructing a Binary Tree from its Traversals", IEEE Comm. , pp. 261-263, 2010
  2. Vinu V Das, "Principles of Data Structures Using C and C++", New Age International Publishers, Reading, Mass. , 2005.
  3. M. Weiss, Data Structures & Problem Solving Using Java, 2"d ed. , Addison Wesley, 2002
  4. D. E. Knuth, The Art of Computer Programming, Vol. 3 (2nd ed. ): Sorting and Searching, Addison Wesley, 1998.
  5. J. Driscoll, and Y. Lien, A Selective Traversal Algorithm for Binary Search Trees, Communications of the ACM, Number 6, Vol. 21, 1978, pp. 445-447.
  6. R. Sedgewick, Algorithms in Java, 3d edition, Addison Wesley, 2003
  7. D. E. Kunth, "The Art of Computer Programming", Vol. 1:Fundamental Algorithm, Addison-Wesley, Reading, Mass. , 1973
  8. 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
  9. 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.
Index Terms

Computer Science
Information Sciences

Keywords

Binary Tree Reconstruction Traversal Non Recursive Algorithm

Powered by PhDFocusTM