CareerCup

We just need to serialize the binary tree in such a way that when we are de-serializing, we can identify the elements in the right and left subtrees. Thus, we can serialize the pre-order traversal of the tree with a special character ('#' etc.) between the left and right subtree of each node. Also, to make things simple, we can insert another special character ('$' etc.) in place of NULL pointers.

Now, we can recursively deserialize, since for each tree, we can always identify the root, elements in the left subtree and elements in the right subtree.

Do a preorder but include the null nodes.

since we have to create the tree by de-serializing the data, so we should serialize in a way that we put the tree in complete binary tree format and put some special character in place of null childs.

preorder will work only for BST. Level order will do the job... (include null nodes)

My code can work:
public static ArrayList<String> Serialize(BinaryTreeNode head){
ArrayList<String> arrayTree=new ArrayList<String>();
serializeProcess(head,arrayTree);
return arrayTree;
}


public static void serializeProcess(BinaryTreeNode head,ArrayList<String> arrayTree){
if(head==null){
arrayTree.add("#");
return;
}
arrayTree.add(String.valueOf(head.value));
serializeProcess(head.leftchild, arrayTree);
serializeProcess(head.rightchild, arrayTree);
}


public static BinaryTreeNode Reconstruct(ArrayList<String> map){
Stack<BinaryTreeNode> holdNode=new Stack<BinaryTreeNode>();
HashMap<BinaryTreeNode,Boolean> definedLeft=new HashMap<BinaryTreeNode,Boolean>();
BinaryTreeNode result=new BinaryTreeNode(Integer.valueOf(map.get(0)));
holdNode.push(result);
for(int i=1;i!=map.size();i++){
BinaryTreeNode current=holdNode.pop();
if(!definedLeft.containsKey(current)){
definedLeft.put(current, true);
if(!map.get(i).equals("#")){
current.leftchild=new BinaryTreeNode(Integer.valueOf(map.get(i)));
holdNode.push(current);
holdNode.push(current.leftchild);
}
else{
holdNode.push(current);
}
}
else{
if(!map.get(i).equals("#")){
current.rightchild=new BinaryTreeNode(Integer.valueOf(map.get(i)));
holdNode.push(current.rightchild);
}
}
}

return result;
}

We could serialize by creating a array of the tree leaving empty positions if no left or right child. And de-serialize it like i root 2i left child 2i+1 right child. Although it will waste space but will give correct result.

The format should be (Left sub tree),(root),(right sub tree). And again each sub tree can be sun divided into (LSB),(ro),(RSB).

While constructing , we should construct the sub tree , with the matching '(' ')'.

Inroder+level-order..is a valid option..

public ArrayList<Integer> serialize(Pair head)
	{
		ArrayList<Integer> al = new ArrayList<Integer>();
		if(head==null)
		{
			al.add(null);
			return al;
		}
		
		Stack<Pair> s = new Stack<Pair>();
		s.push(head);
		while(!s.empty())
		{
			Pair node = ( Pair) s.pop();
			if(node==null)
			{
				al.add(null);
			}
			else
			{
                                s.push(node.second);
				s.push(node.first);
				al.add(node.val);
			}
			
		}
		return al;
		
	}
	
	
	public Pair cons_tree(Iterator<Integer> al)
	{
		Pair p = new Pair(null, null , 0);
		
		Integer i = al.next();
		if(i == null)
		{
			p = null;
			return p;
		}
		p.val = i;
		p.first = cons_tree(al);
		p.second = cons_tree(al);
		return p;
		
		
	}

Do a BFS and send $ instead of NULLs.