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


     / \                                                
    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 ?


1 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.

  1. 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.

  1. 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
  • $\begingroup$ geeksforgeeks.org/serialize-deserialize-binary-tree if you look to this, under "How to store a general Binary Tree?" they write "We can save space by storing Preorder traversal and a marker for NULL pointers" Does it mean that the PREORDER storing N is unique? $\endgroup$
    – Giacomo
    Nov 7, 2019 at 10:43
  • $\begingroup$ Yes preorder traversal with markers as in this question uniquely determines binary key. $\endgroup$ Nov 7, 2019 at 14:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.