  There exists a bijection between one stack sortable permutations
--permutations which avoid the pattern 231-- and planar trees. We define an
edit distance between permutations which is coherent with the standard edit
distance between trees. This one-to-one correspondence yields a polynomial
algorithm for the subpermutation problem for $(231)$ avoiding permutations.
Moreover, we obtain the generating function of the edit distance between
ordered trees and some special ones. For the general case we show that the mean
edit distance between a planar tree and all other planar trees is at least
$n/ln(n)$. Some results can be extended to labeled trees considering colored
Dyck paths or equivalently colored one stack sortable permutations.
