Sunday, March 27, 2011

Serializing a binary tree

Q: Design an algorithm and write code to serialize and deserialize a binary tree.

Advantages of serialization/deserialization include storing a binary into and restoring it for a later point of time, transmitting the tree over a network from one computer and load it in another computer.

One approach for this problem could be the nodes with NULL values using some kind of sentinel so that later nodes can be inserted In correct place while deserialization. Lets use the sentinel as # and we will use preorder traversal here serialization.

Assume we have a binary tree below:

The preorder traversal of the above tree can be written as 

30 10 50 # # # 20 45 # # 35 # #

No comments: