The Binary Tree Roll Operation: Definition, Explanation and Algorithm

Abstract

The paper introduces an operation on a binary tree, called binary tree roll, or roll of a binary tree. Two versions of the binary tree roll, counterclockwise and clockwise, are presented. The operations are mathematically defined and graphically presented. It is explained how the binary tree roll actually coincides with the process of turning the entire tree 90 degrees counterclockwise or clockwise. To visually explain and perform the roll operation, the concepts of a wedge node, true ancestor, illusory ancestor, illusory root and illusory ancestral stem of nodes are introduced, as well as the visual operations of turning and downshift. Both roll operations are implemented using programming algorithms. The algorithms are explained, and all the situations that might be encountered during processing the roll operation are examined and resolved. Thus, the paper gives a mathematical introduction of both binary tree roll operations, gives their visual explanations and offers algorithms for their implementations using a computer.