Which Tree traversal String is unique?

Question

Assume we have a tree and we want to serialize it.

Example:

Tree
                              
      1                                                  
     / \                                                
    3   2                                       
   / \ / \                                 
  5  N N  N   
 / \
N   N

can result as:

"1,3,5,N,N,N,2,N,N", // Pre Order serialization;
"N,5,N,3,N,1,N,2,N", // In Order serialization;
"N,N,5,N,3,N,N,2,1", // Post Order serialization

I would like to know, which one of these three serializations is unique for all trees and why ?

Answer 1

Preorder traversal:

This traversals always yield unique binary trees. For a proof, please check why recording non-existent children in the pre-order traversal will differentiate different binary trees?.

For instance consider traversal sequence $6,5,N,N,5,3,N,N,2,N,N$.

We can proceed as follow to construct binary tree.

1. First symbol is always root of tree.

Root will always be identified uniquely.

2. Try to parse remaining part of input recursively(This will be our left sub-tree). When one sub-tree is parsed return.

Here this left sub-tree parsing will start with input $5,N,N,5,3,N,N,2,N,N$ and will return after input $5,3,N,N,2,N,N$ left to be processed.

3. Try to parse yet remaining part of input recursively(This will be our right sub-tree).

---

Post-order traversal: This is similar to pre-order.

---

inorder traversal: This does not always yield unique binary tree. Here is counterexample.

Consider preorder traversal $N,5,N,6,N,3,N,5,N,2,N$. And following two binary trees.

        6                    5
       /  \                /  \
      5    5              6    2
     / \  /  \           / \  / \
    N  N 3    2         5   3 N  N
        / \  / \       / \ / \
       N   N N  N     N  N N  N