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