“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 33
School of Mathematics
  Title:   On the generation of binary trees from (0-1) codes
1.  A. Nowzari-Dalini
2.  H. Ahrabian
  Status:   Published
  Journal: Int. J. Comput. Math.
  Vol.:  69
  Year:  1998
  Pages:   243-251
  Supported by:  IPM
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 Cn 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.

Download TeX format
back to top
scroll left or right