rahul_1234's blog

Serialise and Deserialise
By rahul_1234, history, 7 years ago, In English

For serialising and deserialising a binary tree( or a n-ary tree ) only preorder traversal with # for Null is used in the given Link but I think both inorder and preorder are required to construct tree.

Please tell me what is that I am missing?

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

In a regular tree, both preorder and postorder are required, because you don't know how many children each node has.

In a binary tree, you know that every node will have exactly two children (they can be null). After you read two children from input, you know you need to backtrack to your parent. If you read the deserialise code this should be clear — you recursively scan in the children, and return to the parent of a node if you finished scanning both children.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So, for binary tree as children are fixed (2), so insertion of NULL helps us to construct tree, which is not so in other case. Please say yes if its correct.

    BTW if there is n-ary tree with n children (0 for leaves), same procedure of serialise and deserialise work (just preorder with NULL)?

    → Reply