Morris' tree traversal algorithm reconsidered

DOI10.1016/0167-6423(88)90063-9MaRDI QIDQ1122985zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Prabhaker Mateti, Ravi Manghirmalani

Publication date 1988

Published in Science of Computer Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6423(88)90063-9

zbMATH Keywords

binary treesMorris' algorithmstack-free algorithmtree traversal

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Algorithms in computer science (68W99)

Review text

Algorithms of D. E. Knuth [\textit{D. E. Knuth}, The art of computer programming, Vol. 1: Fundamental Algorithms (Addison Wesley, (1968; Zbl 0191.179)] and of J. M. Morris [\textit{J. M. Morris}, Traversing binary trees simply and cheaply, Inf. Process. Lett. 9, 197-200 (1979; Zbl 0422.68028)] for traversing binary trees are reproduced and discussed. As result it is shown that the Morris algorithm uses a stack what is not seen at the first glance. In this formal proof, control structure transformations are used.

Recommendations

• A study of binary tree traversal algorithms and a tag-free threaded representation
• A bounded-space tree traversal algorithm
• A trivial algorithm whose analysis is not: a continuation
• A taxonomy of binary tree traversals
• Parallel algorithms for tree traversals

Cited in

(6)

• A taxonomy of binary tree traversals
• Trees with the mos subtrees - an algorithmic approach
• Automated Verification of the Deutsch-Schorr-Waite Tree-Traversal Algorithm
• scientific article; zbMATH DE number 3982557 (Why is no real title available?)
• A study of binary tree traversal algorithms and a tag-free threaded representation
• A bounded-space tree traversal algorithm

This page was built for publication: Morris' tree traversal algorithm reconsidered

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1122985)