Problem

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.

Clarification: The input/output 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.

Examples

Example 1:

1
2

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

Input format

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        
    }
}

Follow up

Serialize and Deserialize N-Ary Tree

Solution

Method 1 - Level Order Traveral 🏆

Example, consider a tree:

1
2
3
4
5
6
7

         20
       /    
      8     
     / \
    4  12 
      /  \
     10  14

Now, we can serialize it to a string like these, treating nulls as ‘#’:

1

20,8,#,4,12,#,#,10,14,#,#,#,#

So, whenever a treenode is null, we have # and we stop tracking the children.

When deserialize the string, I assign left and right child for each not-null node, and add the not-null children to the queue, waiting to be handled later.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

public class Codec {

	public String serialize(TreeNode root) {
		if (root == null) {
			return "";
		}

		StringBuilder sb = new StringBuilder();

		Queue<TreeNode> queue = new LinkedList<TreeNode>();

		queue.add(root);

		while (!queue.isEmpty()) {
			TreeNode t = queue.poll();

			if (t != null) {
				sb.append(String.valueOf(t.val) + ",");
				queue.add(t.left);
				queue.add(t.right);
			} else {
				sb.append("#,");
			}
		}

		sb.deleteCharAt(sb.length() - 1);
		return sb.toString();
	}

	public TreeNode deserialize(String data) {
		if (data == null || data.length() == 0) {
			return null;
		}

		String[] arr = data.split(",");
		TreeNode root = new TreeNode(Integer.parseInt(arr[0]));

		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.add(root);

		int i = 1;

		while (!queue.isEmpty()) {
			TreeNode t = queue.poll();

			if (t == null) {
				continue;
			}

			if (!arr[i].equals("#")) {
				t.left = new TreeNode(Integer.parseInt(arr[i]));
				queue.offer(t.left);

			} else {
				t.left = null;
				queue.offer(null);
			}

			i++;

			if (!arr[i].equals("#")) {
				t.right = new TreeNode(Integer.parseInt(arr[i]));
				queue.offer(t.right);

			} else {
				t.right = null;
				queue.offer(null);
			}

			i++;
		}

		return root;
	}
}

Method 2 - Preorder(or Postorder) and Inorder Traversal

A simple solution is to store both Inorder and Preorder traversals. This solution requires requires space twice the size of Binary Tree.

Construct Binary Tree from Inorder and Preorder Traversal Construct Binary Tree from Inorder and Postorder Traversal

Method 3 - Using Preorder Traversal

We can save space by storing Preorder traversal and a marker like # for NULL pointers.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

Input:
     12
    /
  13
Output: 12 13 # # #

Input:
      20
    /   \
   8     22 
Output: 20 8 # # 22 # #

Input:
         20
       /    
      8     
     / \
    4  12 
      /  \
     10  14
Output: 20 8 4 # # 12 10 # # 14 # # #

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

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

	Stack<TreeNode> stack = new Stack<TreeNode> ();
	stack.push(root);
	StringBuilder sb = new StringBuilder();

	while (!stack.isEmpty()) {
		TreeNode h = stack.pop();
		if (h != null) {
			sb.append(h.val + ",");
			stack.push(h.right);
			stack.push(h.left);
		} else {
			sb.append("#,");
		}
	}

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

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
	if (data == null)
		return null;

	int[] t = { 0 };
	String[] arr = data.split(",");

	return helper(arr, t);
}

public TreeNode helper(String[] arr, int[] t) {
	if (arr[t[0]].equals("#")) {
		return null;
	}

	TreeNode root = new TreeNode(Integer.parseInt(arr[t[0]]));

	t[0] = t[0] + 1;
	root.left = helper(arr, t);
	t[0] = t[0] + 1;
	root.right = helper(arr, t);

	return root;
}

Method 4 - Using Preorder Recursion and List.toString()

Using the recursion for the above logic, and toString() on the list:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

public class Codec {
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serialize(root, sb);
        return sb.toString();
    }
    
    public void serialize(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append("#").append(",");
        } else {
            sb.append(root.val).append(",");
            serialize(root.left, sb);
            serialize(root.right, sb);
        }
    }


// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
	Queue<String> strList = new LinkedList<String> (Arrays.asList(strArray));
	return deserializeHelper(strList);
}

private TreeNode deserializeHelper(Queue<String> strList) {
	String s = q.poll();
	if (s.equals("#")) return null;
	TreeNode root = new TreeNode(Integer.parseInt(s));
	root.left = deserialize(q);
	root.right = deserialize(q);
	return root;
}