There are two nice tree constructions, that use a stack in a similar manner:
Construct a binary search tree from a pre-order traversal (e.g. see http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversal-set-2/)
Construct a Cartesian tree from an array of numbers (e.g. https://en.wikipedia.org/wiki/Cartesian_tree)
I feel like these could be more or less the same thing, if looked from a proper angle, but I can't find a unified way to look at them. Any suggestions?
UPDATE: this is actually pretty cute: both are related to so-called stack-sortable permutations (https://en.wikipedia.org/wiki/Stack-sortable_permutation): rotating a properly labeled cartesian tree gives its preorder traversal, which can be used to recover the tree using the first construction.