Linear random generation of Motzkin trees

Motzkin trees are also called unary-binary trees. This paper proposes a linear algorithm for uniform random generation of Motzkin trees. The algorithm uses the same paradigm as this of R{\'e}my's linear algorithm for random generation of binary trees and is based on a preliminary computation.