Abstract
A survey of the literature shows that eleven binary tree traversals have been defined. We systematize this work by proposing a classification that consists of twenty-six traversals grouped into seven categories. Three generator schemas are provided that allow all of the traversals to be implemented.
Similar content being viewed by others
References
E. N. Adams,Another representation of binary tree traversal, Inf. Proc. Letters 2 (1973), 52–54.
R. R. Atkinson, B. H. Liskov and R. W. Scheifler,Aspects of implementing CLU, Proc. ACM Annual Conf., Washington DC, 1978, pp. 123–129.
A. T. Berztiss,Data Structures: Theory and Practice, 2nd ed. Academic Press, New York, 1975.
A. T. Berztiss,Depth-first K-trees and critical path analysis, Acta Inf. 13 (1980), 325–346.
A. T. Berztiss,Data abstraction, controlled iteration, and communicating processes, Proc. ACM Annual Conf., Nashville TN, 1980, pp. 197–203.
A. Blikle,Addressless units for carrying on loop-free computations, J. ACM 19 (1972), 136–157.
W. A. Burkhard,Nonrecursive tree traversal algorithms, Computer J. 18 (1975), 227–230.
J. A. Goguen, J. W. Thatcher and E. G. Wagner,An initial algebra approach to the specification, correctness, and implementation of abstract data types, in Current Trends in Programming Methodology, Vol. 4: Data Structuring (R. T. Yeh, ed.). Prentice-Hall, Englewood Cliffs NJ, 1978, pp. 80–149.
R. E. Griswold and M. T. Griswold,The Icon Programming Language. Prentice-Hall, Englewood Cliffs NJ, 1983.
D. Gries and N. Gehani,Some ideas on data types in high-level languages, Comm. ACM 20 (1977), 414–420.
J. V. Guttag, E. Horowitz and D. R. Musser,The design of data type specifications, in Current Trends in Programming Methodology, Vol. 4: Data Structuring (R. T. Yeh, ed.). Prentice-Hall, Englewood Cliffs NJ, 1978, pp. 60–79.
D. E. Knuth,The Art of Computer Programming, Vol. 1: Fundamental Algorithms. Addison-Wesley, Reading MA, 1968, p. 329 (Exercise 4).
D. E. Knuth,The Art of Computer Programming, Vol. 3: Sorting and Searching. Addison-Wesley, Reading MA, 1973.
B. W. Lampson, J. J. Horning, R. L. London, J. G. Mitchell and G. J. Popek,Report on the programming language Euclid, ACM SIGPLAN Notices 12, 2 (Feb. 1977).
L. S. Levy,Ordering of trees — simplified proofs, Proc. 7th Ann. Princeton Conf. Inf. Sciences and Systems 1973, 400–402.
B. Liskov, R. Atkinson, T. Bloom, E. Moss, J. C. Schaffert, R. Scheifler and A. Snyder,CLU Reference Manual. Springer-Verlag LNCS 114, Springer-Verlag, Berlin, 1981.
W. J. Meyers,Linear representation of tree structure, Proc. 3rd Ann. ACM Symp. Theory Computing 1971, 50–62.
Z. Pawlak,New class of mathematical languagues and organization of addressless computers. Proc. Colloq. Foundations Math., Math. Machines and their Applications, Tihany, Hungary, 1962, 227–238.
L. A. Rowe and K. A. Shoens,Data abstraction, views and updates in Rigel, Proc. ACM SIGMOD 1979 Internat. Conf. Management Data, 71–81.
M. Shaw (ed.),Alphard: Form and Content. Springer-Verlag, New York, 1981.
R. Tarjan,Depth-first search and linear graph algorithms, SIAM J. Comput 1 (1972), 146–160.
L. E. Thorelli,Marking algorithms, BIT 12 (1972), 555–568.
J. P. Tremblay and P. G. Sorenson,An Introduction to Data Structures with Applications. McGraw-Hill, New York, 1976.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Berztiss, A. A taxonomy of binary tree traversals. BIT 26, 266–276 (1986). https://doi.org/10.1007/BF01933706
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01933706