Groupon Interview Question
SDE1sCountry: United States
Send binary tree as an array.
A binary tree can be put in the array very easily. child of nodes of "i" are located at "2*i" and "2*i+1". So just pass him as a stream of numbers starting from the array index 1. You have to send the first number to be the number of nodes in the tree, so that server can allocate the array.
You are describing a heap. binary tree is not necessarily a heap.
But, you can make it a heap by stubbing the NULL leaves, and then you can serialize it out the way you described.
To deserialize, I think it's easier to just reconstruct the tree then using an array.
A binary tree is not necessarily a heap, but a heap is necessarily some sort of tree, usually (but not always, see Fibonacci heap) binary.
As mentioned any two traversal can be sent for syncing details between client and server.
I would send to the server in the in-order format {{1, 2, {3, 4, null}}, 5, {7, {null, 8, 6}, 9}}, there will be 3 elements in the curly brace representing left, root and right, you can as well put them as left, root, right for easier construction of tree on the server. On the server we would construct a tree using the java class, so that it will be easier for other operations on the tree.
List<Character> serialization(Node root) {
List<Character> list=new ArrayList<Character>();
if(root==null) {
list.add('#');
} else {
list.add(root.val);
list.addAll(serialization(root.left));
list.addAll(serialization(root.right));
}
return list;
}
Node deSerialization(List<Character> list) {
char c=list.get(0);
list.remove(0);
if(c=='#') return null;
Node root=new Node(c);
root.left=deSerialization(list);
root.right=deSerialization(list);
return root;
}
You can send the tree as preorder and in order traversals or XML tree and then parse to reconstruct the tree.
- Expressions April 03, 2013