For some variants of RMQ data structures, the number of Cartesian trees (i.e. the Catalan numbers) is a part of the running-time analysis. What are some other examples where the Cataln numbers show up (either in a data structure itself or in a run-time analysis)?
-
2$\begingroup$ Applications in combinatorics - you will find an algorithmic problem for the most of this applications.. $\endgroup$ – Danny Apr 17 '14 at 7:57