Another Solution to Knuth’s Tree Traversal Problem

Abstract

In 1968, Donald Knuth posed the following problem on binary tree traversals which has engaged computer scientists ever since: Design a non-recursive algorithm that, without using an auxiliary stack, traverses an unthreaded binary tree in which one bit of temporary storage is allowed in each node. The tree can be modified in any way but must be restored to its original state before the algorithm ends. To date, several solutions to Knuth’s problem have been published. The best-known and quite elegant solution to this problem is the Morris algorithm, which also solves Knuth’s 1973 reformulation of the problem which disallows the use of any temporary storage bits (e.g., tag bits). But because the Morris algorithm dynamically threads the tree and then uses these threads during the traversal, the Morris algorithm arguably violates the requirement that the tree be unthreaded. Moreover, because its use of some of the right links in the tree essentially constitutes a stack, it also arguably violates the requirement that the algorithm be stack free. Of course, it can equally well be argued that the Morris algorithm is indeed a solution, given that Knuth’s problem states that the tree can be modified in any way as long as it is restored to its original state. The Schorr-Waite algorithm avoids the need for a stack by inverting the parent-to-child links to the child-to-parent orientation as it advances down the tree. The inverted links are then used to backtrack whenever a branch in the tree has been fully traversed. However, this algorithm requires a tag field it each node. Thus, it violates the requirement of the 1973 version of Knuth’s problem that temporary storage cannot be used. The Robson algorithm uses the same link-inversion technique as the Schorr-Waite algorithm. But it does not use tag fields. In place of the tag bits, it uses an internal stack (a stack dynamically created within the tree using the link fields that contain null pointers). Thus, it violates Knuth’s requirement that an auxiliary stack cannot be used. The algorithm we present uses neither an internal nor an external stack. Thus, it truly is a stack-free algorithm. Moreover, it does not modify the tree in any way during execution. Thus, multiple processes can traverse the same tree concurrently. The algorithm is applicable to any binary tree with the standard structure except that the link fields must contain address differences rather than absolute addresses. We call such a tree a D-tree (“D” for difference). The use of address differences in the link fields of the tree is what makes backtracking possible without the use of a stack. In a D-tree, backtracking and advancing, each requires only one computation (a subtraction to backtrack and an addition to advance). Highlights: • Another solution to Knuth’s tree traversal problem • A stack-free unthreaded tree traversal algorithm that does not modify the tree • A new representation of a binary tree.