CareerCup

This problem may seem intimidating at first, but if you look at the tree as a special case of a graph, it's not that hard.

Perform a BFS traversal of the tree, but print the children count of a node before printing the children themselves. So, serializing is just doing a BFS, attaching the number of children before actually printing the children.

Example for a tree of integers (applies similarly to a tree of strings). If you have this tree:

1 5 2 3 4 5 6 3 7 8 9 1 10 2 11 12 0 3 13 14 15 0 0 0 0 0 0 0 0 0

This is the serialized version of a tree with the following properties:

The root is 1. 1 has 5 children; they are 2, 3, 4, 5 and 6.
2 has 3 children; they are 7, 8, 9
3 has 1 child; it is 10
4 has 2 children: 11 and 12
5 has no children
6 has 3 children: 13, 14, 15
7 has no children
8 has no children
9 has no children
10 has no children
11 has no children
12 has no children
13 has no children
14 has no children
15 has no children

Deserializing is easy. You use another queue. Initialize the queue with the first node read. Then until the queue becomes empty, dequeue a node, read the children count from input, and then read that same amount of nodes and enqueue them as you read them.

Working C++ implementation:

#include <iostream>
#include <vector>
#include <queue>
#include <sstream>

using namespace std;

struct tree_node {
	int val;
	vector<tree_node *> children;
	tree_node(int v) : val(v) { }
};

string serialize(tree_node *root) {
	if (root == NULL)
		return "";

	queue<tree_node*> queue;
	ostringstream oss;

	queue.push(root);
	oss << root->val;

	while (!queue.empty()) {

		tree_node *curr = queue.front();
		queue.pop();
		oss << " " << curr->children.size();

		for (vector<tree_node*>::const_iterator it = curr->children.begin();
		     it != curr->children.end();
		     it++) {
			oss << " " << (*it)->val;
			queue.push(*it);
		}
	}

	return oss.str();
}

tree_node *deserialize(const string &tree_str) {
	if (tree_str == "")
		return NULL;

	queue<tree_node*> queue;
	istringstream iss(tree_str);
	int value;
	iss >> value;

	tree_node *root = new tree_node(value);
	queue.push(root);

	while (!queue.empty()) {
		tree_node *curr = queue.front();
		queue.pop();
		int count;
		iss >> count;
		for (int i = 0; i < count; i++) {
			iss >> value;
			tree_node *new_node = new tree_node(value);
			curr->children.push_back(new_node);
			queue.push(new_node);
		}
	}

	return root;
}

static void destroy_tree(tree_node *root) {
	if (root == NULL)
		return;
	for (vector<tree_node*>::iterator it = root->children.begin();
	     it != root->children.end();
	     it++)
		destroy_tree(*it);
	delete root;
}

int main(void) {
	cout << "Enter an N-ary tree as described in the comments to deserialize and serialize it again" << endl;
	cout << "> ";

	string input;
	while (getline(cin, input)) {
		cout << serialize(deserialize(input)) << endl;
		cout << "> ";
	}

	return 0;
}

List<String> serialization (TreeNode root){
List<String> rst = new ArrayList<String>();
if(root == null)
return rst;
preorder(root, rst);
return rst;
}

void preorder(TreeNode root, List<String> rst){
rst.add(root.name);
for(TreeNode child : root.children){
preorder(child, rst);
}
rst.add(“)”);
}

TreeNode deserialization(List<String> list){
if(list == null || list.size() == 0)
return null;
TreeNode root = new TreeNode(list.get(0));
list.remove(0);
while( !list.get(0).equals(“)”) ){
TreeNode child = deserialization(list);
if(child != null)
root.children.add(child);
}
list.remove(0);
return root;
}

List<String> serialization (TreeNode root){
List<String> rst = new ArrayList<String>();
if(root == null)
return rst;
preorder(root, rst);
return rst;
}

void preorder(TreeNode root, List<String> rst){
rst.add(root.name);
for(TreeNode child : root.children){
preorder(child, rst);
}
rst.add(“)”);
}

TreeNode deserialization(List<String> list){
if(list == null || list.size() == 0)
return null;
TreeNode root = new TreeNode(list.get(0));
list.remove(0);
while( !list.get(0).equals(“)”) ){
TreeNode child = deserialization(list);
if(child != null)
root.children.add(child);
}
list.remove(0);
return root;
}

Using python.
Keeping parents in a stack.

class TreeNode(object):

    def __init__(self, data):
        self.data = data
        self.childs = []

    def print_me(self):
        tmp = [str(self.data)]
        if self.childs:
            tmp.append('(')
            for child in self.childs:
                tmp.append(child.print_me())
            tmp.append(')')
        return ''.join(tmp)


def serialize(root):
    if not root:
        return ''

    tmp = [str(root.data)]
    if root.childs:
        tmp.append('(')
        for child in root.childs:
            tmp.append(serialize(child))
        tmp.append(')')
    return ''.join(tmp)


def deserialize(tree_string):
    if not tree_string:
        return None

    root = TreeNode(int(tree_string[0]))
    parents_stack = [root]
    helper(tree_string, 1, parents_stack, root)
    return root


def helper(tree_string, i, ps, prev):
    if i == len(tree_string):
        return

    cur = tree_string[i]

    if cur == ')':
        ps.pop()
    elif cur == '(':
        ps.append(prev)
    else:
        prev = TreeNode(cur)
        ps[len(ps) - 1].childs.append(prev)

    helper(tree_string, i + 1, ps, prev)


test_tree = deserialize('1')
assert serialize(test_tree) == test_tree.print_me()
print test_tree.print_me()

test_tree = deserialize('1(2(9)34(56(78)))')
assert serialize(test_tree) == ftest_treeoo.print_me()
print test_tree.print_me()

Using python. keeping parents in a stack.

class TreeNode(object):

    def __init__(self, data):
        self.data = data
        self.childs = []

    def print_me(self):
        tmp = [str(self.data)]
        if self.childs:
            tmp.append('(')
            for child in self.childs:
                tmp.append(child.print_me())
            tmp.append(')')
        return ''.join(tmp)


def serialize(root):
    if not root:
        return ''

    tmp = [str(root.data)]
    if root.childs:
        tmp.append('(')
        for child in root.childs:
            tmp.append(serialize(child))
        tmp.append(')')
    return ''.join(tmp)


def deserialize(tree_string):
    if not tree_string:
        return None

    root = TreeNode(int(tree_string[0]))
    parents_stack = [root]
    helper(tree_string, 1, parents_stack, root)
    return root


def helper(tree_string, i, ps, prev):
    if i == len(tree_string):
        return

    cur = tree_string[i]

    if cur == ')':
        ps.pop()
    elif cur == '(':
        ps.append(prev)
    else:
        prev = TreeNode(cur)
        ps[len(ps) - 1].childs.append(prev)

    helper(tree_string, i + 1, ps, prev)


test_tree = deserialize('1')
assert serialize(test_tree) == test_tree.print_me()
print test_tree.print_me()

test_tree = deserialize('1(2(9)34(56(78)))')
assert serialize(test_tree) == test_tree.print_me()
print test_tree.print_me()

my python solution with test. uncomment to see print

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class Solution:
    def __init__(self):
        self.pre = []
        self.ino = []

    def preorder(self, root, list):
        if not root:  return
        list.append(root.val)
        self.preorder(root.left, list)
        self.preorder(root.right, list)

    def inorder(self, root, lists):
        if not root:  return
        self.inorder(root.left, lists)
        lists.append(root.val)
        self.inorder(root.right, lists)

    def serialization(self, root):
        self.preorder(root, self.pre)
        self.inorder(root, self.ino)

    def de_serial(self):
        return self.de_serialization(self.pre, self.ino)

    def de_serialization(self, pre, inorder):
        if not pre:  return None
        root = Node(pre[0])
        i = 0
        while i < len(inorder):
            if pre[0] == inorder[i]:
                break
            i += 1

        root.left = self.de_serialization(pre[1:i+1], inorder[:i])
        root.right = self.de_serialization(pre[i+1:], inorder[i+1:])
        return root


if __name__ == "__main__":
    a = Solution()
    tree = Node(0)
    tree.left = Node(1)
    tree.right = Node(2)
    a.serialization(tree)
    root = a.de_serial()
    print root.val, root.left.val, root.right.val

My python solution with test. Uncomment print statement to see output.

class Node:
    def __init__(self, val):
        self.val = val
        self.sons = []

class Solution:
    def __init__(self, root):
        self.sequence = str(root.val)
        cur = [root]
        while cur:
            next = []
            for i in cur:
                self.sequence += str(len(i.sons))
                for ii in i.sons:
                    next.append(ii)
                    self.sequence += str(ii.val)
            cur = next

    def de_serial(self):
        strs = self.sequence
        # print strs
        idx = 1
        cur = [Node(int(strs[0]))]
        root = cur[0]
        while idx < len(strs):
            next = []
            for i in cur:
                num = int(strs[idx])
                # print 'num', num
                idx += 1
                for j in range(num):
                    tmp = Node(int(strs[idx]))
                    # print tmp.val
                    i.sons.append(tmp)
                    next.append(tmp)
                    idx += 1

            cur = next
            # print map(lambda x: x.val, next)
        return root

if __name__ == "__main__":
    tree = Node(1)
    two = Node(2)
    three = Node(3)
    four = Node(4)
    five = Node(5)
    six = Node(6)
    seven = Node(7)
    tree.sons = [two, three, four]
    two.sons = [five]
    three.sons = [six, seven]
    a = Solution(tree)
    print a.de_serial()

sorry I submitted twice

Assuming a n-ary tree + preserving order in which the nodes appear.

For marshalling => Perform a DFS traversal of the tree. For each visit of the node print out ...,[value of the node]number of children,...
For unmarshalling => Use a stack to place unpopulated nodes. For each new node read, pop out nodes equal to the children of the node being looked at. populate children in reverse order of the recently popped out nodes.

Solution in C++

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <stack>

using namespace std;

struct Node {
  string val;
  vector<Node*> children;
};

class TreeSerializer {
  static char DELIM;

  stringstream _serialStream;

  public:
  string serializeTree(const Node* const root);
  Node* deserializeTree(const string& serialStr);
  
  protected:
  void serializeInner(const Node* const root);
};

char TreeSerializer::DELIM = '!';

string TreeSerializer::serializeTree(const Node* const root) {
  _serialStream.str("");
  serializeInner(root);
  return _serialStream.str();
}

void TreeSerializer::serializeInner(const Node* const root) {
  if (root == nullptr) return;

  _serialStream << root->val << DELIM
    << root->children.size() << DELIM; 

  for (const Node* const child : root->children) {
    serializeInner(child);
  }
}

Node* TreeSerializer::deserializeTree(const string& serialStr) {
  if (serialStr.empty()) return nullptr;

  istringstream iss(serialStr);
  string token;

  stack<Node*> pointers;
  Node* pRoot = new Node;
  pointers.push(pRoot);

  while (getline(iss, token, DELIM)) {
    Node* pNode = pointers.top();
    pointers.pop();

    pNode->val = token;

    getline(iss, token, DELIM);
    int childrenCount = stoi(token);
    pNode->children = vector<Node*>(childrenCount);

    for (int i = childrenCount - 1; i >= 0; --i) { 
      Node* pChild = new Node;
      pNode->children[i] = pChild;
      pointers.push(pChild);
    }
  }

  return pRoot;

}

int main() {

  Node* root = new Node;
  root->val = "root";

  Node* child1 = new Node;
  child1->val = "child1";

  Node* child2 = new Node;
  child2->val = "child2";

  Node* child11 = new Node;
  child11->val = "child11";

  root->children.push_back(child1);
  root->children.push_back(child2);
  child1->children.push_back(child11);

  TreeSerializer serializer;
  string serial = serializer.serializeTree(root);
  cout << "Serial string: " << serial << endl;

  Node* deserial = serializer.deserializeTree(serial);

  cout << deserial->val << endl 
    << deserial->children[0]->val << endl
    << deserial->children[1]->val << endl
    << deserial->children[0]->children[0]->val << endl;

  return 0;
}

#include <iostream>
using namespace std;

int getCount(int N) {
  if (N <= 0) { return 0; }
  if (N == 1) { return 10; }
  int counts[2][10] = { { 0, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, { } };
  int *pPrevCounts;
  int *pCounts;
  for (int iDigit = 1; iDigit < N; ++iDigit) {
    pPrevCounts = &counts[!(iDigit % 2)][0];
    pCounts = &counts[(iDigit % 2)][0];
    for (int i = 0; i <= 9; ++i) {
      for (int j = i - 4; j >= 0; --j) {
        pCounts[j] += pPrevCounts[i];
      }
      for (int j = i + 4; j <= 9; ++j) {
        pCounts[j] += pPrevCounts[i];
      }
    }
  }
  int result = 0;
  for (int i = 0; i <= 9; ++i) {
    result += pCounts[i];
  }
  return result;
}

int main() {
  int N = 10;
  cout << getCount(N) << endl;
  return 0;
}

How about, print preorder and inorder of the tree and send them both. Then form the tree using those on the other machine?

Provide another idea, we can process this problem like son.

struct Node {
	Node(const string &v) : val(v) {}
	
	string val;
	vector<Node*> sons;
};


void doMarshal(Node *root, string &data) {
	if (root == nullptr)
		return;
	data.push_back('{');
	data += root->val;
	data.push_back(':');
	for (Node *c : root->sons)
		doMarshal(c, data);
	data.push_back('}');
}

string Marshal(Node *root) {
	string data;
	doMarshal(root, data);
	return data;
}


Node *doUnmarshal(const string &data, string::size_type &pos) {
	if (pos >= data.size())
		return nullptr;
	++pos;
	string::size_type npos = data.find(':', pos);
	Node *root = new Node(data.substr(pos, npos - pos));

	pos = npos + 1;
	while (data[pos] != '}') {
		root->sons.push_back(doUnmarshal(data, pos));
	}
	++pos;
	return root;
}

Node *Unmarshal(const string &data) {
	string::size_type pos = 0;
	return doUnmarshal(data, pos);
}

My idea is to do a DFS of the tree with a modification of adding the parent after traversing one of its child. For example, if the tree is like this
0->1, 2, 3
1->4, 5, 6, 7
2-> 8, 9
3->10

The serialized version would be this:
0 1 4 1 5 1 6 1 7 1 0 2 8 2 9 2 0 3 10 3 0

When deserializing, we use a stack to reconstruct the tree. We initialize the stack with the first element of the list. In the above case, 0. In the next iteration, we pop the top of the stack and add the next element in the list as a child to the top. If the current element is same as the value of the peek, we ignore. I have a working code below. But not sure if this solution works for all the cases:

public class SerializeAndDeserializeNAryTree {
    public static void main(String[] args)
    {
        NAryTree tree = new NAryTree();
        NAryTreeNode root = new NAryTreeNode(0);
        tree.root = root;
        NAryTreeNode one = new NAryTreeNode(1);
        NAryTreeNode two = new NAryTreeNode(2);
        NAryTreeNode three = new NAryTreeNode(3);
        NAryTreeNode four = new NAryTreeNode(4);
        NAryTreeNode five = new NAryTreeNode(5);
        NAryTreeNode six = new NAryTreeNode(6);
        NAryTreeNode seven = new NAryTreeNode(7);
        NAryTreeNode eight = new NAryTreeNode(8);
        NAryTreeNode nine = new NAryTreeNode(9);
        NAryTreeNode ten = new NAryTreeNode(10);
        root.children.add(one);
        root.children.add(two);
        root.children.add(three);
        one.children.add(four);
        one.children.add(five);
        one.children.add(six);
        one.children.add(seven);
        two.children.add(eight);
        two.children.add(nine);
        three.children.add(ten);
        List<Integer> serializedTree = tree.Serialize();
        for(int i = 0; i < serializedTree.size(); i++)
        {
            System.out.print(serializedTree.get(i)+" ");
        }
        
        System.out.println();
        NAryTree deserializedTree = new NAryTree(serializedTree);
        List<Integer> serializedTreeAgain = deserializedTree.Serialize();
        for(int i = 0; i < serializedTreeAgain.size(); i++)
        {
            System.out.print(serializedTreeAgain.get(i)+" ");
        }
    }
}

class NAryTree
{
    NAryTreeNode root;
    NAryTree()
    {
        this.root = null;
    }
    
    NAryTree(List<Integer> serializedTree)
    {
        Stack s = new Stack();
        for(int i = 0; i < serializedTree.size(); i++)
        {
            Integer cur = serializedTree.get(i);
            if (s.isEmpty())
            {
                this.root = new NAryTreeNode(cur);
                s.push(root);
            }
            else
            {
                NAryTreeNode top = (NAryTreeNode)s.pop();
                if (s.isEmpty() || ((NAryTreeNode)s.peek()).node != cur)
                {
                    NAryTreeNode temp = new NAryTreeNode(cur);
                    top.children.add(temp);
                    s.push(top);
                    s.push(temp);
                }
            }
        }
    }
    
    List<Integer> Serialize()
    {
        if (this.root == null)
        {
            return null;
        }
        
        List<Integer> serializedTree = new ArrayList<Integer>();
        SerializeRecursive(this.root, null, serializedTree);
        return serializedTree;
    }
    
    void SerializeRecursive(NAryTreeNode root, NAryTreeNode parent, List<Integer> serializedTree)
    {
        if (root == null)
        {
            return;
        }
        
        serializedTree.add(root.node);
        for(int i = 0; i < root.children.size(); i++)
        {
            SerializeRecursive(root.children.get(i), root, serializedTree);
        }
        
        if (parent != null)
        serializedTree.add(parent.node);
    }
    
    void Deserialize()
    {
        
    }
}

class NAryTreeNode
{
    int node;
    List<NAryTreeNode> children;
    NAryTreeNode(int node)
    {
        this.node = node;
        this.children = new ArrayList<NAryTreeNode>();
    }
}