## Amazon Interview Question

Software Engineer / Developers**Country:**United States

**Interview Type:**In-Person

This is a fine answer, and it's basically using "#" as a sentinel for null. If your binary tree contained characters, and "#" was a valid value, you'd need to escape values of "#" to make this work.

btw - the interviewer said "binary tree contains integers", so this solution is perfectly fine. It also the same as interviewer suggested in the end )

Why there is an index parameter in the deserialize method...looks like unused...........

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).

```
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;
}
```

void serialize(struct Node *node,char arr[],int &index)

- Anonymous February 26, 2013{

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;

}