A New Method for Threading Binary-Trees

This contribution presents an additional improvement for binary-tree threading. By rearrangement of threading pointers, an entirely threaded binary-tree can be obtained, without additional memory requirement. This is achieved by assuring that each binary-tree node has a pointer to its successor (or predecessor). In this way, traversing of this binary-tree is as easy as traversing the linear list. We confirmed experimentally that the traversing of binary trees is considerably faster in comparison with traditional threading.