# Which Tree traversal String is unique?

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 ?

• pre-order traversal will be "1,3,5,N,N,N,2,N,N" for your tree. Jul 26, 2021 at 6:44

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
• 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" Nov 4, 2019 at 14:47
• @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? Nov 4, 2019 at 15:42
• "1,3,5,N,2,N,N" I added the three possible serializations in the question Nov 4, 2019 at 15:51
• 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? Nov 4, 2019 at 16:00
• yes you are right Nov 4, 2019 at 16:02