Building Cartesian trees from free trees with k leaves

• We propose faster algorithms for building Cartesian trees from free trees.
• We derive matching lower bounds for our algorithms.
• Our results highlight interesting structural properties of Cartesian trees.

One can build a Cartesian tree from an n-element sequence in O(n) time, and from an n-node free tree in time (with a matching worst-case lower bound in the comparison model of computation). We connect these results together by describing a Cartesian tree construction algorithm based on a “bitonicity transform” running in time on a free tree with k leaves, noting that a path is the special case of a tree with just 2 leaves. We also provide a matching worst-case lower bound in the comparison model.