Research Article
Modified Non-Recursive Algorithm for Reconstructing a Binary Tree
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 43 - Issue 10 |
| Published: April 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 },
year = { 2012 },
volume = { 43 },
number = { 10 },
pages = { 25-28 },
doi = { 10.5120/6141-8386 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2012
%A Nitin Arora
%A Vivek Kumar Tamta
%A Suresh Kumar
%T Modified Non-Recursive Algorithm for Reconstructing a Binary Tree%T
%J International Journal of Computer Applications
%V 43
%N 10
%P 25-28
%R 10.5120/6141-8386
%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
- Vinu V Das, "A new Non-Recursive Algorithm for Reconstructing a Binary Tree from its Traversals", IEEE Comm. , pp. 261-263, 2010
- Vinu V Das, "Principles of Data Structures Using C and C++", New Age International Publishers, Reading, Mass. , 2005.
- M. Weiss, Data Structures & Problem Solving Using Java, 2"d ed. , Addison Wesley, 2002
- D. E. Knuth, The Art of Computer Programming, Vol. 3 (2nd ed. ): Sorting and Searching, Addison Wesley, 1998.
- 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.
- R. Sedgewick, Algorithms in Java, 3d edition, Addison Wesley, 2003
- D. E. Kunth, "The Art of Computer Programming", Vol. 1:Fundamental Algorithm, Addison-Wesley, Reading, Mass. , 1973
- 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
- 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
Keywords