  Generalizing stack sorting and $c$-sorting for permutations, we define the
permutree sorting algorithm. Given two disjoint subsets $U$ and $D$ of $\{2,
\dots, n-1\}$, the $(U,D)$-permutree sorting tries to sort the permutation $\pi
\in \mathfrak{S}_n$ and fails if and only if there are $1 \le i < j < k \le n$
such that $\pi$ contains the subword $jki$ if $j \in U$ and $kij$ if $j \in D$.
This algorithm is seen as a way to explore an automaton which either rejects
all reduced expressions of $\pi$, or accepts those reduced expressions for
$\pi$ whose prefixes are all $(U,D)$-permutree sortable.
