Generation of binary trees from (0-1) codes

Abstract

A Binary tree can be represented by a code reflecting the traversal of the corresponding regular binary tree in a given monotonic order. A different coding scheme based on the branches of a regular binary tree with n-nodes is proposed. It differs from the coding scheme generally used and makes no distinction between internal nodes and terminal nodes. A code of a regular binary tree with n-nodes is formed by labeling the left branches by 0's and the right branches by 1's and then traversing these branches in pre-order. Root is always assumed to be on a left branch. Different order of traversals yield different codes. An efficient nonrecursive Pascal program of 0(nlog₂ n) time complexity using the backtracking approach is given to generate these codes in colexicographic order.

Keywords:

• Code
• Traversals
• monotonic Order
• Binary trees
• Recurson
• Backtrack approach
• Algorithm Design

C.R. Categories:

• G 2.1 Combinatorial algorithm
• G 2.2 Graph Theory