How many traversals need to be known to construct a BST
algorithm, binary-search-tree, inorder, postorder, preorder
Solution
To construct a BST you need only one (not in-order) traversal.
In general, to build a binary tree you are going to need two traversals, in order and pre-order for example. However, for the special case of BST - the in-order traversal is always the sorted array containing the elements, so you can always reconstruct it and use an algorithm to reconstruct a generic tree from pre-order and in-order traversals.
So, the information that the tree is a BST, along with the elements in it (even unordered) are equivalent to an in-order traversal.
Bonus: why is one traversal not enough for a general tree, (without the information it is a BST)? Answer: Let's assume we have `n` distinct elements. There are `n!` possible lists to these `n` elements, however - the possible number of trees is much larger (2 * n! possible trees for the n elements are all decayed trees, such that `node.right = null` in every node, thus the tree is actually a list to the right. There are `n!` such trees, and another n! trees where always `node.left = null` ) Thus, from pigeon hole principle - there is at least one list that generates 2 trees, thus we cannot reconstruct the tree from a single traversal. (QED)
Problem
I am very confused by a number of articles at different sites regarding constructing a `Binary Search Tree` from any one traversal (`pre`,`post` or `in-order`), or a combination of any two of them. For example, at this page, it says that given the `pre`,`post` or `level` order traversal, along with the `in-order` traversal, one can construct the `BST`. But here and there, they show us to construct a `BST` from `pre-order` alone. Also, here they show us how to construct the `BST` from given `pre` and `post-order` traversals. In some other site, I found a solution for constructing a `BST` from the `post-order` traversal only. Now I know that given the `inorder` and `pre-order` traversals, it is possible to uniquely form a `BST`. As regards the first link I provided, although they say that we can't construct the `BST` from `pre-order` and `post-order`, can't I just sort the `post-order` array to get its `inorder` traversal, and then use that and the `pre-order` array to form the `BST`? Will that be same as the solution in the 4th link, or different? And given `pre-order` only, I can sort that to get the `in-order`, then use that and the `pre-order` to get the `BST`. Again, does that have to be different from the solution at links 2 and 3? Specifically, what is sufficient to uniquely generate the `BST`? If uniquement is not required, then I can simply sort it to get the `in-order` traversal, and build one of the N possible `BST`s from it recursively.