Amazon Interview Question
Software Engineer / DevelopersCountry: 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;
}