Twist-Rotation Transformations of Binary Trees and Arithmetic Expressions

Abstract

The paper studies the computational complexity and efficient algorithms for the twist-rotation transformations of binary trees, which is equivalent to the transformation of arithmetic expressions over an associative and commutative binary operation. The main results are (1) a full binary tree with n labeled leaves can be transformed into any other in at most 3n log n + 2n twist and rotation operations, (2) deciding the twist-rotation distance between two binary trees is NP-complete, and (3) the twist-rotation transformation can be approximated with ratio 6 log n + 4 in polynomial time for full binary trees with n uniquely labeled leaves. © 1999 Academic Press.