Interview Question
Team: SQL Server / DPG Group
Country: United States
Interview Type: In-Person
Assuming every node contains 26 pointers, a node can be represented using 4 bytes (the first 6 representing the node information and the next 26 indicating the presence of child pointers)[1]
Traverse pre-order. Write '0' for an internal node and '1' for a leaf node. Write the 4 bytes representing the node after that. Do a breadth first traversal on the tree and keep writing these 4 bytes one after the other. You will end up taking 4n bytes to represent the tree.
While deserializing, create blocks of 4 bytes each and put it in a queue. Dequeue to get the first node. Make it the root. Then dequeue k blocks where k is the number of children of the root, attach them appropriately. Move to the first child node which has non-zero children. Repeat process.
[1] Assumption for ease of implementation. There may be other ways.
I can see a simple extension to the algorithm mentioned in the wiki to satisfy a general k-array tree without using a bit more or less.
I actually misread your post.
You have the same argument as mentioned in the wiki, except that you encode data along with the child nodes presence (0 or 1). Whereas the wiki keeps them separate.
I'm not sure about your assumption "using 6 bits for storing node information...".
So yep, all is well.
use Breadth-first search.
- BeautifulCode October 15, 2012