On the generation of binary trees from (0–1) codes

Abstract

An efficient recursive a algorithm for the generating all shapes of binary trees with n-nodes is presented. A binary tree with n-nodes is represented by 2(n−1) zeros and ones in a certain predetermined order. This scheme encodes the non-null links of a binary tree by 1's and the null links by 0's in a pre-order traversal. The algorithm generates C _n numbers of such codes. The algorithm is based on the idea of shifting ‘1' bits one space to the right. It is shown that the generation time per tree is constant O(1). The ranking and unranking algorithms are discussed. Also, an alternate way to obtain the Catalan numbers is given.

Keywords:

• Binary tree
• code
• recursion
• traversal

C.R. Categories:

• G.2.1 Combinatorial Algorithm
• G.2.2 Graph Theory (Trees)

^∗Corresponding author.

^∗Corresponding author.

Notes

^∗Corresponding author.

Additional information

Notes on contributors

A. Nowzari-Dalini

b