### Generating binary trees using rotationsGenerating binary trees using rotations

Access Restriction
Subscribed

 Author Zerling, David Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1985 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract A new algorithm that, for the first time, exploits the rotational geometry of binary trees is developed in order to allow for the lexicographic generation of computer representations of these trees in average time $\textit{O}(1)$ per tree. “Rotation” codewords for these trees (in average time $\textit{O}(1)$ per tree) are also generated. It is shown how these codewords relate to lattice paths, and, using this relationship, that $\textit{n}(\textit{n}$ - $1)/(\textit{n}$ + 2) is the average number of rotations needed to generate a binary tree on $\textit{n}$ nodes. Finally, a necessary and sufficient condition that a codeword represent a full binary tree (each node has 0 or 2 sons) on $\textit{n}$ = $2\textit{m}$ + 1 nodes is given and how to contract this codeword to obtain the codeword for the binary tree on $\textit{m}$ nodes for which this full tree is the extended binary tree is shown. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1985-07-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 32 Issue Number 3 Page Count 8 Starting Page 694 Ending Page 701

#### Open content in new tab

Source: ACM Digital Library