Serialize and Deserialize Binary Tree

LeetCode Q 297 - Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Example:
You may serialize the following tree: as “[1,2,3,null,null,4,5]”
Clarification: The above format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

Solution :

You can find Binary Tree Representation in BFS here

Solution 1 : DFS

Code:

// Encodes a tree to a single string.
public String serialize(TreeNode root) {
	if (root == null) return "#";

	return root.val + "," + serialize(root.left) + "," + serialize(root.right);
}


// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
	String[] strs= data.split(",");
	return deserializeDFS(strs, new int[] {0});
}

private TreeNode deserializeDFS(strs, int[] index) {
	if (strs[index[0]].equals("#")) {
		index[0]++; return null;
	} 

	TreeNode root = new TreeNode (Integer.parseInt(strs[index[0]]));
	index[0]++;
	root.left = deserializeDFS(strs, index);
	root.right = deserializeDFS(strs, index);

	return root;
}

Solution 2 : BFS

Code:

// Encodes a tree to a single string.
public String serialize(TreeNode root) {
	if (root == null) return "#";

	StringBuilder sb = new StringBuilder();
	Queue<TreeNode> que = new LinkedList<>();
	que.offer(root.val);

	while (!que.isEmpty()) {
		TreeNode curr = que.poll();
		if (curr == null) {
			sb.append("#");
		} else {
			sb.append(curr.val);
			que.offer(curr.left);
			que.offer(curr.right);
		} 
		que.offer(",");
	}

	return sb.toString.substring(0, sb.length());
}


// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
	if (data.equals("#")) return null;
	
	String[] strs = data.split(",");
	Deque<TreeNode> que = new ArrayDeque<>();
	TreeNode head = new TreeNode(Integer.parseInt(strs[0]));
	que.offer(head);
	
	int idx = 1;
	while (idx < s.length()) {
		TreeNode curr = que.poll();
		if (strs[idx].equals('#')) {
			curr.left = null;
		} else {
			curr.left = new TreeNode(Integer.parseInt(strs[idx]));
			que.offer(cur.left);
		}

		idx++;

		if (strs[idx].equals('#')) {
			curr.right = null;
		} else {
			curr.left = new TreeNode(Integer.parseInt(strs[idx]));
			que.offer(cur.left);
		}

		idx++;
	}

	return head;
}