A study of binary tree traversal algorithms and a tag-free threaded representation

Abstract

Starting from a stack-based binary tree traversal algorithm for preorder and/or inorder, we derive an algorithm recently discovered by J. M. Morris which requires neither stack nor tag fields. This algorithm may also be derived from the familiar threaded binary tree traversal algorithm. By demonstrating how searching may proceed in parallel with traversal, we show that the algorithm is “almost read-only”. This leads to a new representation for threaded binary trees requiring no tag fields. We show how to perform the usual operations efficiently for this representation, including strictly read-only traversal. In addition, we analyse the performance of variants of the traversal algorithm for binary trees represented with/without threads and with/without tag fields.

Keywords:

• Trees
• Traversals
• Novel Tag-Free Threaded Representation

C.R. Categories:

• E.l[Data]
• Data Structures-trees
• F.2.2 [Analysis of Algorithms and Problem Complexity]
• Nonnumerical Algorithms and Problems-traversals