1
$\begingroup$

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,2,N,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 ?

$\endgroup$
2
$\begingroup$

Preorder traversal:

This traversals always yield unique binary trees. (proof for this remains. To me it seems that it is correct due to procedure to construct tree that follows. However it might not be the case.)

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
$\endgroup$
  • $\begingroup$ I think you misunderstood the question. I agree with you that traversals are not unique, but in this case, I am not only inserting the values in an array, I am also inserting the null elements "N" $\endgroup$ – Giacomo Nov 4 '19 at 14:47
  • $\begingroup$ @Giacomo yes you're write. But I think it would be good if we also include $N,N$ symbols for leaf node. For instance preorder traversal of tree given in question would be $1,3,5,N,N,N,2,N,N$ am I correct? Or am I missing something? $\endgroup$ – Vimal Patel Nov 4 '19 at 15:42
  • 1
    $\begingroup$ "1,3,5,N,2,N,N" I added the three possible serializations in the question $\endgroup$ – Giacomo Nov 4 '19 at 15:51
  • $\begingroup$ Yes you have added three possible serialization but my question is that when there is no child for a node than we use $N$ to denote that, that pointer is null. Am I write? $\endgroup$ – Vimal Patel Nov 4 '19 at 16:00
  • $\begingroup$ yes you are right $\endgroup$ – Giacomo Nov 4 '19 at 16:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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