Tree traversal and serialization

Question

I am trying to get straight in my head how tree traversals can be used to uniquely identify a tree, and the crux of it seems to be whether the tree is a vanilla Binary Tree (BT), or if it also has the stricter stipulation of being a Binary Search Tree (BST). This article seems to indicate that for BT's, a single inorder, preorder and postorder traversal will not uniquely identify a tree (uniquely means structure and values of keys in this context). Here is a quick summary of the article:

BTs
1. We can uniquely reconstruct a BT with preorder + inorder and postorder + inorder.
2. We can also use preorder + postorder if we also stipulate that the traversals keeps track of the null children of a node.

(an open question (for me) is if the above is still true if the BT can have non-unique elements)

BSTs
3. We cannot use inorder for a unique id. We need inorder + preorder, or inorder + postorder.

Now, (finally) my question is, can we use just pre-order or just post-order to uniquely identify a BST? I think that we can, since this question and answer seems to say yes, we can use preorder, but any input much appreciated.

Answer 1

I can't tell what's being asked here. Any binary tree, whether it's ordered or not, can be serialized by writing out a sequence of operations needed to reconstruct the tree. Imagine a simple stack machine with just two instructions:

• Push an empty tree (or NULL pointer if you like) onto the stack

• Allocate a new internal node N, stuff a value into N, pop the top two trees off the stack and make them N's left and right children, and finally push N onto the stack.

Any binary tree can be serialized as a "program" for such a machine. The serialization algorithm uses a postorder traversal.

Answer 2

Okay, you can use preorder only to identify a tree. This is possible because only in preorder traversal does the id-of-current-node comes before the ids of children. So you can read the traversal output root-to-leaves.

You can check http://en.wikipedia.org/wiki/Tree_traversal#Pre-order to confirm

So you can consider a preorder traversal as a list of insertions into a tree. Because the tree insertion into BST is deterministic, when you insert a list of values into an empty tree, you always get the same tree.