A single traversal algorithm for serializing any binary tree

Abstract

It is possible to save a binary tree to a file and restore it at a later time. Because these two operations are frequently necessary and therefore important, an efficient algorithm to represent a binary tree in a compact way is very desirable. For special types of binary trees, there are efficient algorithms, otherwise, there is a method that stores both the inorder and either preorder traversal or postorder traversal of the binary tree which requires two traversals of the binary tree during construction of the storage array. In this paper, I present an approach for which only one traversal is sufficient for construction of the storage array. I also present a more efficient complement algorithm for restoration of the binary tree.