CareerCup

***serialization***

1. traverse tree using level order traversal
2. If a node dont have left or right child while serializing in its place serialize $(or any other sentinel value)

***deserialization***
1.read values from file (It is in level order)
2. if value is not sentinel thn it is a node add it to tree
3. make it child of its parent if current loop count is odd it is left child else it is right child
4. if it is a sentinel value set null in the left or right(whichever it is) pointer of parent

complexity o(n) for both operations

Serialize node recursively as
NODE LEFT RIGHT
use ^ if node doesn't have a right child
A binary tree

'
                            10
	  5                                 18 
1                8              13               20
              7                        14

would become the string '10 5 ^ 8 7 ^ ^ 18 13 14 ^ 20'

deserialize:
1. read value by value
2. if value is sentinal
no more children
3. smaller than current node's key it is left-child
otherwise right-child

class NodeDS:
    def __init__( self, key ):
        self.key = key
        self.left=None
        self.right=None

def serialize_tree( node ):
    if not node:
        return ''
    s = '%d '%node.key
    s += serialize_tree( node.left )
    if node.right is None:
        s += '^ '
    else:
        s += serialize_tree( node.right )
    return s

class TagStream:
    def __init__( self,input_string ):
        self.tags=input_string.split()
        self.index = 0

    def next( self ):
        tag =  self.tags[self.index]
        self.index += 1
        return tag

def _deserialize_tree( stream, last_key = None ):
    node = NodeDS(last_key)
    while True:
        next_key = stream.next()
        if next_key == '^': break
        next_node = _deserialize_tree( stream, int(next_key) )
        if int(next_key)<last_key:
            node.left = next_node
        else:
            node.right = next_node
            break
    return node

def deserialize_tree( input ):
    stream = TagStream( input )
    first_key = stream.next()
    return _deserialize_tree( stream, int(first_key) )

what kind of binary tree, just simple BT or BST?

Solution 1. Store each value with its parent (0 parent if it is the root) also specifying if it is left or right child
Solution 2. Store the inorder and preorder traversal (or inorder and postorder).

From these it is easy to get the original tree.

Do level by level traversal of the tree and serialize nodes. For Eg:

1
	2	         	3
4		          5	      7

Serialize it as " 1 $ 2 3 $ 4 NULL 5 7 $ "
Here $ indicates the end of a level. NULL indicates that child is not present.
Space : O(2^(height of tree+1)) - 1 + height

How about:

offset_t serialize(n)
{
    if (n == NIL) return -1;            // offset -1 for NIL node

    n->left = serialize(n->left);
    n->right = serialize(n->right);

    offset = dump_node(n);  // returns the offset the dump file

    return offset;
}

serialize(root);
dump_node(dummy);  // dump a dummy node as the end of serialization

deserialize(input)
{
    map = create a map (offset, node);   // map the offset to node

    map[-1] = NIL;

    while ( n = read one node from input) {
        if (n is the dummy node)
            return;

        map[current_offset] = n;

        n->left = map[n->left]
        n->right = map[n->right]
    }
}

I think serialization should be done for two traversal for same BST
1. Preorder/Postorder and Inorder
2. While de-serializing create the tree by using both traversal. This will make sure that order of tree doesn't change

I have thise as an answer to your question. Only problem in this solution is I am failing to guess where EOF file is encountering.
{{
public void serializeBinaryTree(BTNode root, ObjectOutputStream oos) throws IOException{
//if nde is null then put some #
String s = "#";
if(root==null){
oos.writeObject("#");
}else{
oos.writeObject(" "+root.data);
serializeBinaryTree(root.left,oos);
serializeBinaryTree(root.right,oos);
}
}

public void dserializeBinaryTree() throws IOException, ClassNotFoundException{
//if nde is null then put some #
String node = null;
FileInputStream fin = new FileInputStream("Tree.ser");
ObjectInputStream ois = new ObjectInputStream(fin);
Scanner input = new Scanner("Tree.ser");
while(true){
System.out.println((String) ois.readObject());
}

}
}}

Serialization of binary tree:

serialization(self):
	if self == None:
		outfile.write("#")
	else:
		outfile.write(self.value)
	serialization(self.left)
	serialization(self.right)