On enumerating tree permutations in natural order
M. C. Er · International Journal of Computer Mathematics · 1987
An efficient algorithm for enumerating all tree permutations of n integers in the natural order is presented. The enumeration problem is solved by considering that a tree permutation hLR is simply a linearized representation of the corresponding binary tree, such that h is the node value and L and R are its left and right subtrees, respectively. The best-case, average-case and worst-case time-complexities of the enumeration algorithm are 0(1)0 (3) and 0(n) respectively, whereas its space-complexity is 0(n). Furthermore, it is shown that the conversion from a tree permutation to the conventional representation of a binary tree using records (nodes) and pointers can be accomplished in 0(n) units of time.