# «Abstract We build upon the previous work on the subset of permutations known as stack words and stack-sortable words. We use preorder, inorder and ...»

Tree Traversals and Permutations

Todd Feil, Kevin Hutson, R. Matthew Kretchmar

Abstract

We build upon the previous work on the subset of permutations

known as stack words and stack-sortable words. We use preorder,

inorder and postorder traversals of binary trees to establish multiple

bijections between binary trees and these words. We show these

operators satisfy a sort of multiplicative cancellation. We further

expand the study of these operators by demonstrating how properties

on trees are related to properties on words.

1 Introduction Knuth [9] considered permutations created by using a stack. Consider pass- ing the sequence 1, 2, 3,..., n through a single stack by means of a series of pushes and pops, where a push will push the next number in the input string and a pop removes the top of the stack to the output string, with the proviso that the stack empties after all integers have been pushed. For example, if n = 4, then the sequence, push, push, pop, push, pop, push, pop, pop, would result in the permutation (2341). (Our convention is to represent the permutation π with the sequence π(1), π(2),..., π(n). Thus, if π = (2341) then π(1) = 2, π(2) = 3, and so on.) Figure 1 shows midway through the creation of the permutation (2341).

It is easy to see that a permutation obtained in this way is a 312-avoiding permutation (For example, see Grimaldi [7].); that is, a permutation π(1), π(2),..., π(n) for which there is no i j k where π(j) π(k) π(i). A permutation π obtained in this manner is called a stack word. For example, the permutation π = (25134) is not 312-avoiding since π(2) = 5, π(4) = 3 and π(5) = 4.

Likewise, a permutation that can be sorted using a stack in the man- ner described is called a stack-sortable word. These are precisely the 231- avoiding permutations; that is, a permutation π for which there is no i j k where π(k) π(i) π(j).

output input output input 1234 2 4 3 1 initial state after push, push, pop, push Figure 1: Creating a stack word Recently, there has been interest in stack words, restricted permuta- tions, stack-sortable words, and their extensions. (See [1], [2], [3], [4], [8], [9], [10], [14], [16], [17], and [18].) Several have related these restricted permutations to various structures, for example, stacks. While bijections between stack words (or stack-sortable words) and binary trees have been given previously (see [4], [6], [15], and especially [9], [12], and [13]), we give additional bijections in which the structure of the tree reﬂects the stack operations in a straightforward manner.

These stack and stack-sortable words can be produced by applying various traversals of binary trees. This idea has been used by [9], [12], [13], and [4]. In eﬀect, we are modeling stack operations with these traversals.

We apply the three common binary tree traversal algorithms of preorder, inorder and postorder to ﬁrst label the tree, then read the labels. The order the labels are read gives us a permutation. That is, for a given binary tree T, we pick a labeling traversal from preorder, inorder and postorder traversals. We then pick a reading traversal from among these three options.

**Thus, we produce a permutation by:**

1. Labeling the nodes of T with 1, 2,..., n using the chosen labeling traversal.

2. Reading the labels from the nodes of T produced in step (1) using the reading traversal.

Note for a given binary tree T, each choice of labeling and reading traversal produces a potentially diﬀerent permutation of 1, 2,..., n. Obviously, if the labeling and reading traversals are the same, the resultant permutation is the identity permutation. If a permutation is obtained from a binary tree by labeling with a preorder traversal and reading with an inorder traversal, we’ll call it a PreIn permutation. Permutations obtained by this process using diﬀerent labeling and reading traversals will be similarly named.

2 In Section 2 we show a bijection between stack words and binary trees which are labeled using an inorder traversal and read using a postorder traversal. That is, we can convert stack words to trees and vice versa.

Section 3 shows how an inorder labeling and a preorder reading produces stack-sortable words. Furthermore, we can produce stack words and stack sortable words with two other label/read traversals.

Section 5 reveals an interesting “canceling” feature of these traversal operators when they are composed. The preorder labeled and postorder read permutations possess some properties not present in the other stack words; these are discussed in Section 6.

We can use a combination of operators to convert from a binary tree to a stack word and then back to another (diﬀerent) binary tree. If we repeat this process, we create a series of trees (and their intervening stack words). This process creates cycles that partition the set of stack words.

We develop an equivalence relation in Section 7.

2 Stack Words, Stack-sortable Words and Binary Trees Notice that the sequence of pushes and pops necessary to produce a stack word (or sort a stack-sortable word) can be conveniently given by a sequence of n pairs of parentheses, where a left parenthesis corresponds to a push and a right parenthesis corresponds to a pop. (This was observed by West [16].) For example, the sequence of pushes and pops producing (2341) can be expressed as (()()()). If you label the parentheses pairs starting at 1, then reading oﬀ the label of the right parentheses will give the corresponding stack word. In our example (1 (2 )2 (3 )3 (4 )4 )1 yields 2341. This establishes a bijection between the set of stack words of length n and the set of n pairs of parentheses.

If π is a stack word, that is, a 312-avoiding permutation of {1, 2,..., n}, then clearly π −1 is a stack-sortable word; that is, a 231-avoiding permutation. Furthermore, the sequence of parentheses (sequence of pushes and pops) that sorts π −1 is precisely the sequence of parentheses that creates π. Thus, the stack word we obtained above, 2341 corresponds to the stacksortable word 4123, which is sorted by the sequence of stack operations given by (()()()).

Now consider binary trees. We describe a bijection between binary trees with n nodes and sequences of n pairs of parentheses. There are many such bijections, of course. For example, see [4] and [6]. The one we give has 3 the advantage of naturally extending to stack words and stack-sortable words. We do this recursively. The empty tree corresponds to zero pairs of parentheses; that is, the empty sequence. A tree of one node corresponds to the sequence (). A tree with more than one node corresponds to the sequence L(R), where L is the sequence of parentheses corresponding to the tree rooted at the left child of the root node and R is the sequence of parentheses corresponding to the tree rooted at the right child of the root node. Some examples are given in Figure 2.

()(()) ()()(()((()))) ((()(()))) Figure 2: Binary trees and nested parentheses The stack word associated with a binary tree T with n vertices can also be realized by labeling the vertices of T with 1, 2,..., n using an inorder traversal and then reading the labels using a postorder traversal. Call such a word an inorder labeled, postorder read word for the tree T and denote the permutation by [In : P ost]T. (This idea is similar to that given in [4].) We formalize this in the following proposition.

Proposition 1 There is a bijection between the inorder labeled, postorder read words and stack words.

Proof: Since stack words are precisely the 312-avoiding permutations, we show that a word is inorder labeled, postorder read if and only if it is 312avoiding. In a binary tree, we’ll say a is a right descendant of b if the node labeled a is in the subtree rooted at the right child of the node labeled b.

Left descendant is similarly deﬁned.

Suppose π is a permutation with a 312 subsequence. Hence there exist i, j, k where i j k with π(j) π(k) π(i). Now if π(j) π(i) on an inordered labeled tree, then one of the three situations hold: (1) π(i) is a right descendant of π(j), (2) π(j) is a left descendant of π(i), or (3) there is some node x where π(i) is a right descendant of x and π(j) is a left descendant of x. These three situations are pictured in Figure 3.

But if i j in the postorder output, only situation (1) can hold. Now, restricting our attention to the situation (1), if π(j) π(k) π(i) either (a) π(k) is a right descendant of π(j) and π(i) is a right descendant of π(k), or (b) π(k) is a left descendant of π(i). These are pictured in Figure 4.

But in postorder output, (a) yields the order π(i), π(k), π(j) and (b) yields π(k), π(i), π(j). In either case, this is not the order desired (π(i), π(j), π(k)). Thus, there is no binary tree T where [In : P ost]T = π.

Now suppose π is a 312-avoiding permutation. We construct the binary tree that is inorder labeled, postorder read that yields π. Since we have a postorder read, label the root node π(n) (the last number in the permutation). Due to the inorder labeling, the right subtree of π(n) will be all nodes labeled π(k) with π(k) π(n) and the left subtree of π(n) will be all nodes labeled π(j) where π(j) π(n). Let L = {π(j) : π(j) π(n)} and R = {π(k) : π(k) π(n)}. We claim that if π(j) ∈ L and π(k) ∈ R, then j k. That is π(j) comes before π(k) in the permutation π. For otherwise we have k j n and π(j) π(n) π(j), which is a 312 subsequence.

We now apply this construction recursively to L and R. Note a postorder reading of the tree will output L, then R, and then π(n). 2 Given the bijection between binary trees and nested parentheses noted before this proposition, one can see there is also a bijection between nested

Note that if [In : P ost]T = π and we label the nodes of the same binary tree T inorder with the labels π −1, then a postorder reading of the nodes will yield the nodes in sorted order 1, 2,..., n. We observed this phenomenon before when we noted that the same stack operations sort π −1 as create π.

One can realize π −1 by labeling the nodes of the InPost tree of π with 1, 2,..., n using a postorder labeling and reading the labels in an inorder traversal. (Similar to our previous notation, we’ll denote such a permutation by [P ost : In]T.) We illustrate with the InPost tree of π = (23154) in Figure 6.

This is true since if we label the InPost tree of π using a postorder labeling, then the label π(i) in the original labeling is replaced by i in the new labeling for each i. Thus each i in the original inorder labeling will be replaced by π −1 (i). Now reading the new labels using an inorder traversal will produce labels in the order π −1 (1),π −1 (2),π −1 (3),..., π −1 (n).

6 3 Stack-sortable Words and Preorder Traversals In light of the above proposition, it is natural to ask what is the permutation that results from an inorder labeled, preorder read tree. Adopting notation

**similar to above, we denote a permutation obtained in this way by [In :**

P re]T. The following proposition answers this, which has been noted in section 2.3.1, exercise 6 of [9] and further exploited in [13] and [12].

Proposition 2 There is a bijection between the inorder labeled, preorder read words and stack-sortable words.

Proof: The proof is similar to the proof of Proposition 1, noting that stacksortable words are precisely those 231-avoiding permutations. When showing that a 231-avoiding permutation, ρ, can be realized as an inorder labeled, preorder read tree, we label the root with ρ(1), the leftmost number of the permutation, and note that all ρ(j) with ρ(j) ρ(1) come before all ρ(k) with ρ(k) ρ(1). As before, we construct the tree recursively. 2 In Figure 7 we illustrate by constructing the inorder labeled, preorder read tree for the stack-sortable word (31254). The reader should note that the tree constructed in this manner does not reﬂect the stack operations necessary to sort the stack-sortable word in a straightforward way. Indeed, the tree structures look very diﬀerent; compare the trees in Figures 6 and

7. Furthermore, if ρ is a stack-sortable word and T is the binary tree so that ρ = [In : P re]T, then the permutation [P re : In]T will be the stack word ρ−1. (See Corollary 1 in Section 5.)

The conversion of a stack word to a preorder labeled, inorder read tree will be used in following sections and so we will illustrate how this tree is constructed directly from the stack word. ([13] and [12] give a similar construction for InPre trees from stack-sortable words.) Note that since T will be preorder labeled, the root node must be labeled with 1. Those values 7 in the stack word to the left of 1 will comprise the left subtree while those to the right of 1 will comprise the right subtree. We apply this technique recursively to each subtree, labeling the root with the smallest number in the subtree. We illustrate this conversion on the stack word (23154) in Figure 8.

If π is a stack word, we call the binary tree T such that [P re : In]T = π the PreIn tree of π.

4 Counting Permutations that are both Stack Words and Stack-sortable Words Rotem [12] counted the number of permutations on {1, 2,..., n} that are both stack words and stack-sortable words, but his proof was diﬃcult and required advanced graph theory techniques and terminology such as interval and permutation graphs. The characterization of stack words on {1, 2,..., n} as a permutation [P re : In]T for some binary tree T with n nodes, as noted in the last section, allows us to perform this count easily.

Since a stack word that is also stack-sortable is a stack word that is 231avoiding, we need only characterize those trees T where [P re : In]T have a 231 subsequence. We then will be able to count the remaining trees with n nodes.

Note that [P re : In]T has a 231 subsequence if and only if there is a left elbow subtree (as shown in Figure 9) in T. The proof of this follows along lines similar to the proof of Proposition 1 and will not be included here.