0
$\begingroup$

I have come across algorithms that can create a BST if any two of the 3 traversals are given (there would be three different algorithms for the 3 combinations)

This is an example

I was wondering, is it guaranteed that a tree generated would be unique? Or rather, can multiple trees be generated satisfying the two traversals?

I am pretty certain that there will only be one tree that satisfies two traversals, because that is how everyone treats the problem, and it seems somewhat logical, but I have never seen it written explicitly anywhere.

Any sources that answer theoretical questions like this about Binary Search Trees would be helpful as well.

$\endgroup$
  • $\begingroup$ If the tree that you want to construct is know to be a BST, then we actually know the inorder traversal, by ordering the nodes from small to large. So, for a BST it suffices to know only the pre-order or post-order in order to reconstruct it. $\endgroup$ – Hendrik Jan May 24 '17 at 14:33
  • 1
    $\begingroup$ There are examples of two different BSTs with the same pre- and postorder traversals. As Hendrick said, though, knowing the inorder traversal and one of the others determines the tree uniquely. $\endgroup$ – Rick Decker May 24 '17 at 16:42