How many workarounds you need to know to build a BST

Question

I am very confused by a number of articles on different sites regarding the construction of a Binary Search Tree from any crawl ( pre , post or in-order ) or a combination of any two of them. For example, the this page says that bypassing the pre , post or level in-order , as well as in-order bypass, you can build a BST . But here and there , they show us the BST design from pre-order . They also show us here how to build a BST from pre and post-order workarounds. In another place, I found a solution to build BST only from the post-order bypass.

Now I know that inorder and pre-order you can uniquely form a BST . Regarding the first link I provided, although they say that we cannot build BST from pre-order and post-order , can I just sort the post-order array to get its inorder bypass and then use this and the array pre-order to form a BST ? Will it be the same as the decision in the 4th link, or another? And just for pre-order , I can sort this to get in-order , and then use it and pre-order to get BST . Again, should this be different from the solution in links 2 and 3?

In particular, what is enough to uniquely generate a BST ? If uniqueness is not required, then I can simply sort it to get an in-order bypass, and build one of N possible BST from it recursively.

Answer 1

To build a BST, you only need one (out of order) workaround.

In general, to create a binary tree, you will need two workarounds, for example, order and pre-order. However, for a special case, a BST crawl in order is always a sorted array containing elements, so you can always restore it and use the algorithm to restore the general tree from preliminary and workarounds.

Thus, the information that the tree is a BST, together with the elements in it (even unordered), is equivalent to a workaround.

Bonus: why is one crawl not enough for a common tree (without information it's BST)?
The answer . Suppose we have n distinct elements. There are n! the possible lists of these elements are n , however - the possible number of trees is much larger (2 * n! Possible trees for n elements are all decomposed trees, such that node.right = null in each node, so the tree is actually the list on the right There are such t21 such trees and other n! Trees, where always node.left = null ). Thus, from the principle of a pigeon hole - there is at least one list that generates 2 trees, so we cannot restore the tree from one bypass. (QED)

Answer 2

If values ​​are specified for BST nodes, only one crawl is sufficient, since the rest of the data is provided by the node values. But if the values ​​are unknown, then, according to my understanding, it is impossible to create a unique BST from one round. However, I am open to suggestions.