CareerCup

Using DFS, we can iterate the tree and create a json object. For each parent node create a child json nodes.
{1:{2:{4:4, 5:5}}, 3:{6:6, 7:7}}}

Simple, user in-order and pre-order traversal to serialize and then deserialize tree.

A tree can be constructed unambiguously if we have 
in-order & pre-order traversal
in-order & post-order traversal
As this may not be a binary tree, so in-order traversal will not be possible.
For a generic tree, one can use DFS and BFS to construct a tree
EX:
Assume for a given tree
DFS  =  c4 , c5, c6, c1, c7 c2, c8 c9, c10, c3, c0
BFS  =  c0 , c1, c2, c3, c4, c5, c6, c7, c8, c9, c10
If we look at the BFS, the first element will be the root
Root = C0
Remove root from BFS & DFS
C1 is the second element in the BFS. 
Locate this C1 in DFS which is at index 3 (index starts at 0), 
Add C1 child of C0
All elements from 0 to 2 are child of C1
Construct the tree with C1 has child’s (c4,c5,c6)
Remove c4,c5,c6,c1 from DFS
Remove c4,c5,c6,c1 from BFS
Iteration-2:
C2 is the second element in the BFS
(At this stage DFS looks like: c7 c2, c8 c9, c10, c3)
(At this stage BFS looks like: c2, c3, c7, c8, c9, c10)

Clearly C2 & C1 are at same level as C2 is not coming in the left of C1 in DFS.
Locate this C2 in DFS which is at index 1 (index starts at 0), 
Add C2 child of C0
element 0 in DFS are child of C2
Construct the tree with C2 has child’s (c7)
Remove c2,c7 from DFS
Remove c2,c7 from BFS
Iteration-3:
C3 is the second element in the BFS
(At this stage DFS looks like: c8 c9, c10, c3)
(At this stage BFS looks like:  c3, c8, c9, c10)

Clearly C3 & C1 are at same level as C3 is not coming in the left of C1 in DFS.
Locate this C3 in DFS which is at index 3 (index starts at 0), 
Add C3 child of C0
element 0 to 2 in DFS are child of C2
Construct the tree with C3 has child’s (c8,c9,c10)
Remove c8,c9,c10,c3  from DFS
Remove c8,c9,c10,c3 from BFS












Input: s1,s2 {s1 is the bfs of the tree, s2 is dfs of the tree}
Output: T (Constructed Tree)
-------------------------------------------------------------
root = s1.first()
remove(root) from s1
remove(root) from s2
T = constructTree(root, null, null) /*construct a tree with only root*/
while (!s1.isEmpty())
{
	e = s1.fist(); /* The first element in the bfs sequence*/
	child[] = {e}
	constructTree(root, child[], T)
	i = indexOf(s2,e) /* get the index of the bfs element in dfs */
	child[] = {s2.getsubsequence(0,i-1)} /* child of e are the left elements of dfs*/
	constructTree(e,child,T)
	remove(childs) from s1
	remove(childs) from s2
}

private final static String P_LEFT = "{", P_RIGHT="}", SEPARATOR=";";
	public String serialize(Node tree){
		StringBuilder sb = new StringBuilder();
		if(tree != null){
			if(tree.value != null){
				sb.append(P_LEFT).append(tree.value);
				List<Node> children = tree.children;//in width traverse
				if(children != null && children.size()>0){
					sb.append(SEPARATOR+P_LEFT);
					for (Node node : children) {
						sb.append(serialize(node));//recursive
						sb.append(SEPARATOR);
					}
					sb.append(P_RIGHT);
				}
				sb.append(P_RIGHT);
			}
		}
		
		return sb.toString();
	}
	
	
	public Node deSerialize(String srcStr){
		Node tree = null;
		if((srcStr != null) && (srcStr.length() >= 2)){
			srcStr = srcStr.substring(1, srcStr.length()-1);//strip {}
			tree = new Node();
			
			//get value
			int firstSeparatorIndx = srcStr.indexOf(SEPARATOR);
			if(firstSeparatorIndx >0){
				String val = srcStr.substring(0, firstSeparatorIndx);
				tree.value = val;
				
				//get children
				String childrenStr = srcStr.substring(firstSeparatorIndx+2, srcStr.length()-1);
				String[] childrenSrcStrs = childrenStr.split(SEPARATOR);
				List<Node> childrenNodes = new ArrayList<Node>();
				for (String string : childrenSrcStrs) {
					Node child = deSerialize(string);
					if(child != null){
						childrenNodes.add(child);//recursive
					}
				}
				tree.children = childrenNodes;
			}else{
				tree.value = srcStr;	
			}
		}
		
		return tree;
	}
	
	public static class Node{
		String value;
		List<Node> children;
	}

Wouldn the simplest be a non binary, left branch only tree. Basically a singly linked list?

Wouldn the simplest be a non binary, left branch only tree. Basically a singly linked list?

Serialization could be something like:

<node1>:<node1 children> | <node2>:<node2 children> ....

where <nodeX> is the serialized string form of nodeX

The problem is how to identify a node uniquely when deserializing the string format.

C++ serialize/deserialize to/from a stream

class Node {
public:
	Data d;
	list<Node*> children;

	void Serialize() {
		// write my data
		cout << d;

		// write the number of children
		cout << children.size();

		// write my children
		for(auto itr=children.begin(); itr != children.end(); ++itr) itr->serialize();
	}

	void deserialize() {
		// read my data
		cin >> d;

		// read my number of children
		int num_children;
		cin >> num_children;

		// read the children
		while(num_children-- > 0) {
			Node* pNode = new Node();
			pNode->deserialize();
			children->push_back(pNode);
		}
	}
};

Everyone seems to assume tree consists of integer or char data.
In practical applications, lots of times data structures hold some complex objects. Your algorithm should you be able to efficiently serialize and deserialize and so your approach should depend on the type of data it holds and how sparse the tree can be.
What if the tree is like a social graph? You can't hold it in memory?
What if this tree has to be sent over the wire? optimize for size of the object there even if it takes little more time to do the serialization and deserialization. etc etc..
These are the things the interviewer will be looking for.

public class Tree {

Tree left;
Tree right;
int val;

static final char START = '[', END = ']', SEPERATOR = ':';
static final String LEAF = "*";

Tree(int val, Tree left, Tree right){
this.val = val;
this.left = left;
this.right = right;
}

String serialize(){
StringBuilder sb = new StringBuilder();
sb.append(START);
sb.append(val);
sb.append(SEPERATOR);
if(left!=null)
sb.append(left.serialize());
else
sb.append(LEAF);
sb.append(SEPERATOR);
if(right!=null)
sb.append(right.serialize());
else
sb.append(LEAF);
sb.append(END);
return sb.toString();
}

static Tree deserialize(String str){
if(str.equals(LEAF)) return null;
int indexSep1 = str.indexOf(SEPERATOR);
int indexSep2 = getMiddleSeperatorIndex(str,indexSep1+1);
int val = Integer.parseInt(str.substring(1, indexSep1));
String leftStr = str.substring(indexSep1+1, indexSep2);
String rightStr = str.substring(indexSep2+1, str.length()-1);
return new Tree(val,deserialize(leftStr), deserialize(rightStr));
}

private static int getMiddleSeperatorIndex(String str, int startIndex) {
int counter = 0;
for (int i = startIndex; i < str.length(); i++) {
char c = str.charAt(i);
if(c == START){
counter++;
}
if(c == END){
counter--;
}
if(c == SEPERATOR && counter == 0){
return i;
}
}
return -1; //error
}

public String toString(){
return serialize();
}

public static void main(String[] args) {
Tree root = new Tree(1, new Tree(2, new Tree(4,new Tree(2,new Tree(1,null,null),null),null), new Tree(5, null, null)),new Tree(3, new Tree(6,null,new Tree(10,null,null)), new Tree(7, null, null)));
System.out.println(root.toString());
Tree root2 = deserialize(root.toString());
System.out.println(root2.toString());
}

}

public class Tree {

	Tree left;
	Tree right;
	int  val;

	static final char START = '[', END = ']', SEPERATOR = ':';
	static final String LEAF = "*";

	Tree(int val, Tree left, Tree right){
		this.val = val;
		this.left = left;
		this.right = right;
	}

	String serialize(){
		StringBuilder sb = new StringBuilder();
		sb.append(START);
		sb.append(val);
		sb.append(SEPERATOR);
		if(left!=null)
			sb.append(left.serialize());
		else
			sb.append(LEAF);
		sb.append(SEPERATOR);
		if(right!=null) 
			sb.append(right.serialize());
		else
			sb.append(LEAF);
		sb.append(END);
		return sb.toString();
	}

	static Tree deserialize(String str){
		if(str.equals(LEAF)) return null;
		int indexSep1 = str.indexOf(SEPERATOR);
		int indexSep2 = getMiddleSeperatorIndex(str,indexSep1+1);
		int val = Integer.parseInt(str.substring(1, indexSep1));
		String leftStr = str.substring(indexSep1+1, indexSep2);
		String rightStr = str.substring(indexSep2+1, str.length()-1);
		return new Tree(val,deserialize(leftStr), deserialize(rightStr));
	}

	private static int getMiddleSeperatorIndex(String str, int startIndex) {
		int counter = 0;
		for (int i = startIndex; i < str.length(); i++) {
			char c = str.charAt(i);
			if(c == START){
				counter++;
			}
			if(c == END){
				counter--;
			}
			if(c == SEPERATOR && counter == 0){
				return i;
			}
		}
		return -1; //error
	}

	public String toString(){
		return serialize();
	}

	public static void main(String[] args) {
		Tree root = new Tree(1, new Tree(2, new Tree(4,new Tree(2,new Tree(1,null,null),null),null), new Tree(5, null, null)),new Tree(3, new Tree(6,null,new Tree(10,null,null)), new Tree(7, null, null)));
		System.out.println(root.toString());
		Tree root2 = deserialize(root.toString());
		System.out.println(root2.toString());
	}

}

can we save the tree structure by saving as pairs of nodes ( parent, child) in the case where a parent can have multiple children ? then, we can serialize each object separately.

(root, a1) <-- root has 2 children a1 and a2
(root, a2)
(a1, b1) <-- a1 has 2 children b1 and b2
( a1, b2)
( a2, b3)
...
then deal with serializing all nodes indiviually as a list or so ?

If the tree is binary tree, then level order traversal is easy for serialize and deserialize.

Serialize:
Do DFS while doing so maintain map table so that key is node and value list of immediate children
Desrialize:
Read each key in map table create node and recursively create it's children