Determine structural equivalence of BSTs with standard traversal

Question

Is it possible to decide the structural equivalence of two binary search trees just with the results of traversals, pre order, in order and post order. Assume I have only the result arrays of all the traversals. I know in order traversal alone, can't help. But, I couldn't visualize for other traversal results. I understand BFS helps. I want to know for Pre and Post order traversals. And if possible, please post any links on this.

Answer 1

The answer is : you can recover a binary search tree from its pre order traversal.

I'm not sure what is your mathematical background so please ask if you need more explanation.

For simplicity, I'm assuming that the node are labeled by the integer 1,2... n where n is the number of node. Then the pre-order traversal of the tree t gives gives you a permutation of [n] = {1,2,...,n} which have a particular property: each time you have a letter b in your permutation, you can't find two consecutive letter ca after the b in the permutation such that a<b<c. Such a permutation is said to avoid the pattern b-ac (the - stand for an arbitrary number of letters).

For example, 4 2 1 3 avoids b-ac whereas 3 1 4 2 doesn't because 3 - 4 2.

This is actually an equivalence: A permutation is the pre order reading of a tree iff is avoid b-ac.

It is know that there are as many trees of size n as permutation avoiding b-ac so this is a bijection. Their number are know as Catalan number. You probably can find this as an exercice of Stanley's book "enumerative combinatorics".

Here is a more algorithmic explanation:

RecTree: Recovering a tree from is Pre-order traversal:

input: list l
output: tree t

b <- l[0]
find an index i such that 
   - for 1<=j<=i then l[j] < b and
   - for i<j<=n  then l[j] > b
if there isn't exists such an index return Failure
else return Node(key=b, RecTree(l[1..i]), RecTree(l[i+1..n]))

As a consequence

Two binary search trees are equal if and only if they have the same pre order traversal

Does it makes sense to you ?

Some more references

• Catalan number in the On-Line Encyclopedia of Integer Sequences
• Anders Claesson Generalized Pattern Avoidance, European Journal of Combinatorics 22 (2001) 961–971

Answer 2

In a BST you can go left child (L), right child (R) or up (U). A traversal can then be described by a string over {L, R, U}, eg. "LLURUURLURUU". For BSTs with equivalent structures, these strings will be identical.