2
$\begingroup$

There are two nice tree constructions, that use a stack in a similar manner:

  1. 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/)

  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.

$\endgroup$
  • $\begingroup$ Welcome to CS.SE! Rather than editing the question to add the answer to the question, I encourage you to write an anwer to your own question, and explain the relationship (e.g., explain how each one is related to stack-sortable permutation, if that is the relationship). Perhaps this will be useful to someone else in the future who is wondering the same thing! $\endgroup$ – D.W. Jun 8 '17 at 18:33
  • $\begingroup$ thanks - I am still working on a comprehensive explanation $\endgroup$ – LazyCat Jun 8 '17 at 20:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.