CareerCup

similar to how heapsort does: http://en.wikipedia.org/wiki/Heapsort
create an array to hold the tree.

left = root * 2
right = root * 2 + 1

use BFS to traversal the tree and place elements into the array. Then serialize the array.

pre-order is enough

What do you mean by serialize a binary tree?

Convert it in an array and then serialize it.

Say, you have:
----1
--2---3
-4-5---7
You need to be able to serialize it to, say, some string and then back.

i think we can use recursion:
make 2 functions - f1( node *n ) and f2( node* n )
f1 returns the tail of serialised tree rooted at node n and f2 returns the head of the serialised tree rooted at n.
All we need to do now is to modify the next ptrs of f1's return value and the current node.

node* f1( node* n ){
if( n==NULL )return n;
if( n->left == NULL && n->right == NULL )return n;
node* c1 = f1( n->left );
node* c2 = f2( n->right );
c1->right = n;
c1->left = NULL;
n->right = c2;
n->left = NULL;
}

Similarly u can write the code for f2() as well. In this I am using the right ptrs for linklist.(any of the two can be used)

Why not post-order/pre-order/in-order?

we can use the combination of tree traversals to build the tree from the traversal array e.g we can use inorder and preorder to store the traversals of the tree and then later on restore the full tree. I think it is not possible to do the same with just a single traversal of any kind.

@T : but that is the only viable option. do you have any other way out to solve it? use the following mail to discuss further.

@ Nitesh : Your solution is wrong. Read my answer properly or you can mail me back for further discussion/advice at yao.saga@hotmail.com.

Loaing an array by using any of the tree traversal methods (in/pre/post/DFS,BFS) is easy. But, how to form a tree back from such an array?

do Bread First Search and store the data of each node in queue. BFS will give nodes level by level. That will help to re-generate the tree in exact form. When de-serializing, deque from the Queue and start creating BST tree.

here I am assuming input tree is BST

Given the inorder and postorder, you can rebuild the tree.

Queue SerializeBT(TreeNode* root)
{
  Queue<Node*> q = new Queue<Node*>();
  if(!root)
    q.enqueue(root);
  else
    SerializeBT(root, q);
  return q;
}

void SerializeBT(TreeNode* node, Queue q)
{
  if(!node)
  {
    q.enqueue(node);
    return;
  }
  
  q.enqueue(node);
  SerializeBT(node->left, q);
  SerializeBT(node->right, q);
  return;
}