# Binary Search Tree: If two different traversals are given, will there be a unique tree that satisfies the traversals? [duplicate]

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.

• 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. – Hendrik Jan May 24 '17 at 14:33
• 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. – Rick Decker May 24 '17 at 16:42