Amazon Interview Question
InternsCountry: India
Interview Type: Phone Interview
Serialize node recursively as
NODE LEFT RIGHT
use ^ if node doesn't have a right child
A binary tree
'
10
5 18
1 8 13 20
7 14
would become the string '10 5 ^ 8 7 ^ ^ 18 13 14 ^ 20'
deserialize:
1. read value by value
2. if value is sentinal
no more children
3. smaller than current node's key it is left-child
otherwise right-child
class NodeDS:
def __init__( self, key ):
self.key = key
self.left=None
self.right=None
def serialize_tree( node ):
if not node:
return ''
s = '%d '%node.key
s += serialize_tree( node.left )
if node.right is None:
s += '^ '
else:
s += serialize_tree( node.right )
return s
class TagStream:
def __init__( self,input_string ):
self.tags=input_string.split()
self.index = 0
def next( self ):
tag = self.tags[self.index]
self.index += 1
return tag
def _deserialize_tree( stream, last_key = None ):
node = NodeDS(last_key)
while True:
next_key = stream.next()
if next_key == '^': break
next_node = _deserialize_tree( stream, int(next_key) )
if int(next_key)<last_key:
node.left = next_node
else:
node.right = next_node
break
return node
def deserialize_tree( input ):
stream = TagStream( input )
first_key = stream.next()
return _deserialize_tree( stream, int(first_key) )
How about:
offset_t serialize(n)
{
if (n == NIL) return -1; // offset -1 for NIL node
n->left = serialize(n->left);
n->right = serialize(n->right);
offset = dump_node(n); // returns the offset the dump file
return offset;
}
serialize(root);
dump_node(dummy); // dump a dummy node as the end of serialization
deserialize(input)
{
map = create a map (offset, node); // map the offset to node
map[-1] = NIL;
while ( n = read one node from input) {
if (n is the dummy node)
return;
map[current_offset] = n;
n->left = map[n->left]
n->right = map[n->right]
}
}
I think serialization should be done for two traversal for same BST
1. Preorder/Postorder and Inorder
2. While de-serializing create the tree by using both traversal. This will make sure that order of tree doesn't change
I have thise as an answer to your question. Only problem in this solution is I am failing to guess where EOF file is encountering.
{{
public void serializeBinaryTree(BTNode root, ObjectOutputStream oos) throws IOException{
//if nde is null then put some #
String s = "#";
if(root==null){
oos.writeObject("#");
}else{
oos.writeObject(" "+root.data);
serializeBinaryTree(root.left,oos);
serializeBinaryTree(root.right,oos);
}
}
public void dserializeBinaryTree() throws IOException, ClassNotFoundException{
//if nde is null then put some #
String node = null;
FileInputStream fin = new FileInputStream("Tree.ser");
ObjectInputStream ois = new ObjectInputStream(fin);
Scanner input = new Scanner("Tree.ser");
while(true){
System.out.println((String) ois.readObject());
}
}
}}
***serialization***
- saumya.tyagi6 January 21, 20141. traverse tree using level order traversal
2. If a node dont have left or right child while serializing in its place serialize $(or any other sentinel value)
***deserialization***
1.read values from file (It is in level order)
2. if value is not sentinel thn it is a node add it to tree
3. make it child of its parent if current loop count is odd it is left child else it is right child
4. if it is a sentinel value set null in the left or right(whichever it is) pointer of parent
complexity o(n) for both operations