Serialization and De-serialization of Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits/bytes so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment. De-serialization is the opposite of serialization, namely, reading the stream of bytes and reconstructing the original data structure/object in memory.

This problem is about de-serialization of a binary tree from a certain format B, and print out its in-order travesal trace.

Constraints:

• There are less than 10,000 nodes in the tree
• Each node consists of left child, right child and a value of int type, which is in the range of [-10,000, 10,000]

Format B is based on the pre-order traversal of the binary tree. The format B serialized string for the shown binary tree is

{3 {9 {} {}} {20 {15 {} {}} {7 {} {}}}}

The format is formally defined as

Tree = {Value {Tree} {Tree}} | {}

{} stands for an empty tree, otherwise Tree is consists of a value and two sub-trees (left, right).

Example 1

Input: 
{3 {9 {} {}} {20 {15 {} {}} {7 {} {}}}}
Output:
9 3 15 20 7