CareerCup

void serialize(struct Node *node,char arr[],int &index)
{
if(!node)
{
arr[index++]='#';
return;
}
arr[index++]=node->data;
serialize(node->left,arr,index);
serialize(node->right,arr,index);
}
struct Node *Deseralize(char arr[],int &size,int &index)
{
if(arr[size]=='#' || size>index)
{
size++;
return NULL;
}
struct Node *node=NewNode(arr[size++]);
node->left=Deseralize(arr,size,index);
node->right=Deseralize(arr,size,index);
return node;
}

Serialize a NULL tree as zero bytes.
Otherwise:
- Serialize the root.
- Serialize 0, 1, 2, or 3 based on whether subtrees exists (0=neither, 1=left only, 2=right only, 3=both)
- Serialize both subtrees

When it comes time to deserialize the tree, the 0/1/2/3 will prevent recursive calls from slurping up data that should belong to the parent nodes:

If no bytes left, return NULL tree.
Read node value.
Read mask.
If mask == 0, return control to caller.
If mask == 1, recursively read left subtree then return.
If mask == 2, recursively read right subtree then return.
If mask == 3, recursively read both trees then returns.

An example serialization might be A3B0C1D2E0, which maps to B <- A -> ((D -> E) <- C).

Another serialization:

tree_rep:
_ => null node
:<tree_rep left>,<serialize value>,<tree_rep right> => regular node

If your tree contains integers, you might have something like this:
:_,2,:_,3,:_,4,_

For serialization
inorder with combination on any other traversal(pre or post) for a BT can be used for serialization
With the inorder and other travesal we can then easily contruct a BT.

template<typename T>
std::ostream &operator<<(std::ostream &out, const BinaryTree<T> &obj)
{
  if (!obj.m_root)
    return out;

  out << obj.SERIAL_ID;
  out << '#';

  typename BinaryTree<T>::Node *node = obj.m_root;
  Stack<typename BinaryTree<T>::Node *> stack;
  while (!stack.isEmpty() || node) {
    if (node) {
      stack.push(node);

      out << node->m_data;
      uint8_t children = 0;
      if (node->m_left)
        children |= obj.LEFT;
      if (node->m_right)
        children |= obj.RIGHT;

      out << children;
      node = node->m_left;
    }
    else {
      stack.pop(node);
      node = node->m_right;
    }
  }
  
  return out;
}

template<typename T>
std::istream &operator>>(std::istream &in, BinaryTree<T> &obj)
{
  int serial;
  char ch;
  in >> serial;
  in >> ch;
  if (serial != obj.SERIAL_ID || ch != '#')
    return in;

  Stack<typename BinaryTree<T>::Node *> stack;

  obj.m_root = new typename BinaryTree<T>::Node;

  typename BinaryTree<T>::Node *node = obj.m_root;

  while (!stack.isEmpty() || node) {
    if (node) {
      stack.push(node);
      T t;
      uint8_t children;

      in >> t;
      in >> children;

      node->m_data = t;

      if (!children)
        stack.pop(node);

      if (children & obj.RIGHT)
        node->m_right = new typename BinaryTree<T>::Node(node, -1);

      if (children & obj.LEFT) {
        node->m_left = new typename BinaryTree<T>::Node(node, -1);
        node = node->m_left;
      }
      else
        node = NULL;
    }
    else {
      stack.pop(node);
      node = node->m_right;
    }
  }

  return in;
}