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

Video explanation

Here is the video explaining below methods in detail. Please check it out:

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.

Complexity

  • ⏰ Time complexity: O(n) – each node is visited/processed a constant number of times during serialization and during deserialization, so work is linear in the number of nodes.
  • 🧺 Space complexity: O(n) – the serialized string and the queue used during BFS can each hold O(n) elements in the worst case.

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

class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (!root) return "";
        string res;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            TreeNode* t = q.front(); q.pop();
            if (t) {
                res += to_string(t->val) + ",";
                q.push(t->left);
                q.push(t->right);
            } else {
                res += "#,";
            }
        }
        if (!res.empty()) res.pop_back();
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(const string& data) {
        if (data.empty()) return nullptr;
        vector<string> arr;
        string token;
        stringstream ss(data);
        while (getline(ss, token, ',')) arr.push_back(token);

        TreeNode* root = new TreeNode(stoi(arr[0]));
        queue<TreeNode*> q;
        q.push(root);
        int i = 1;
        while (!q.empty() && i < (int)arr.size()) {
            TreeNode* cur = q.front(); q.pop();
            if (arr[i] != "#") {
                cur->left = new TreeNode(stoi(arr[i]));
                q.push(cur->left);
            }
            i++;
            if (i < (int)arr.size() && arr[i] != "#") {
                cur->right = new TreeNode(stoi(arr[i]));
                q.push(cur->right);
            }
            i++;
        }
        return root;
    }
};
 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

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;
	}
}
 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

from collections import deque

class Codec:
    def serialize(self, root: 'TreeNode') -> str:
        if not root:
            return ""
        res = []
        q = deque([root])
        while q:
            node = q.popleft()
            if node:
                res.append(str(node.val))
                q.append(node.left)
                q.append(node.right)
            else:
                res.append("#")
        return ",".join(res)

    def deserialize(self, data: str) -> 'TreeNode':
        if not data:
            return None
        arr = data.split(',')
        root = TreeNode(int(arr[0]))
        q = deque([root])
        i = 1
        while q and i < len(arr):
            node = q.popleft()
            if arr[i] != '#':
                node.left = TreeNode(int(arr[i]))
                q.append(node.left)
            i += 1
            if i < len(arr) and arr[i] != '#':
                node.right = TreeNode(int(arr[i]))
                q.append(node.right)
            i += 1
        return root

Method 2 - Preorder(or Postorder) and Inorder Traversal

A simple solution is to store both Inorder and Preorder/Postorder traversals. This solution requires requires space twice the size of Binary Tree. Also, it will be harder to complete the solution in a single interview setting.

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

Complexity

  • ⏰ Time complexity: O(n) – building traversals and reconstructing the tree from inorder+preorder (or inorder+postorder) requires linear time when using index maps.
  • 🧺 Space complexity: O(n) – storing two traversals and auxiliary maps/recursion uses linear space.

Method 3 - Using Iterative 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 # # #

Complexity

  • ⏰ Time complexity: O(n) – serialization visits each node once; deserialization processes each token once while rebuilding the tree recursively.
  • 🧺 Space complexity: O(n) – worst-case stack/recursion depth and serialized string size are linear in the number of nodes.

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

class Codec {
public:
	// Encodes a tree to a single string (iterative preorder with null markers).
	string serialize(TreeNode* root) {
		if (!root) return "";
		string res;
		stack<TreeNode*> st;
		st.push(root);
		while (!st.empty()) {
			TreeNode* node = st.top(); st.pop();
			if (node) {
				res += to_string(node->val) + ",";
				st.push(node->right);
				st.push(node->left);
			} else {
				res += "#,";
			}
		}
		if (!res.empty()) res.pop_back();
		return res;
	}

	// Decodes your encoded data to tree using recursive helper and an index.
	TreeNode* deserialize(const string& data) {
		if (data.empty()) return nullptr;
		vector<string> arr;
		string token;
		stringstream ss(data);
		while (getline(ss, token, ',')) arr.push_back(token);
		int idx = 0;
		return helper(arr, idx);
	}

private:
	TreeNode* helper(const vector<string>& arr, int& idx) {
		if (idx >= (int)arr.size()) return nullptr;
		if (arr[idx] == "#") { idx++; return nullptr; }
		TreeNode* node = new TreeNode(stoi(arr[idx]));
		idx++;
		node->left = helper(arr, idx);
		node->right = helper(arr, idx);
		return node;
	}
};
 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

public class Codec {
	// 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;
	}
}
 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

class Codec:
	def serialize(self, root: 'TreeNode') -> str:
		if not root:
			return ""
		res = []
		stack = [root]
		while stack:
			node = stack.pop()
			if node:
				res.append(str(node.val))
				# push right first so left is processed next
				stack.append(node.right)
				stack.append(node.left)
			else:
				res.append("#")
		return ",".join(res)

	def deserialize(self, data: str) -> 'TreeNode':
		if not data:
			return None
		arr = iter(data.split(','))

		def helper():
			val = next(arr)
			if val == '#':
				return None
			node = TreeNode(int(val))
			node.left = helper()
			node.right = helper()
			return node

		return helper()

Method 4 - Using Recursive Preorder

Intuition

A single traversal like pre-order is not enough because it doesn’t capture the tree’s shape. For example, a pre-order sequence of [1, 2] could mean 2 is the left child of 1 OR the right child of 1. This ambiguity means crucial structural information is lost.

The key insight is that to preserve the tree’s structure, we must also preserve its emptiness. By augmenting the traversal to record null nodes (e.g., with a # marker), a single traversal becomes sufficient. The ambiguity is now resolved: a sequence of [1, 2, ...] definitively means 2 is the left child, while a sequence of [1, #, 2, ...] means 2 is the right child.

Approach

Serialization
  • Perform a pre-order traversal (Node -> Left -> Right) on the tree.
  • When visiting a node, append its value to a list.
  • If a node is null, append a special marker (e.g., #) to the list.
  • Join the list elements to form a single, comma-separated string.
Deserialization
  • Split the serialized string into a queue of values.
  • Create a recursive build function that processes the queue.
  • Inside the build function, dequeue a value.
  • If the value is the null marker, return null.
  • Otherwise, create a new TreeNode with the value.
  • Crucially, make a recursive call to build to construct the node’s left child, and then another recursive call to construct its right child.
  • The pre-order sequence of the data ensures that the tree is reconstructed in the correct order. This approach is robust and works for all binary trees, including those with duplicate values.

Complexity

  • ⏰ Time complexity: O(n) – a single preorder traversal (with null markers) serializes the tree and deserialization consumes each token once to rebuild the tree recursively.
  • 🧺 Space complexity: O(n) – the serialized representation and recursion stack (worst-case) use linear space.

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

class Codec {
public:
    const string SEP = ",";
    const string NULLT = "#";

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        vector<string> res;
        buildList(root, res);
        string out;
        for (size_t i = 0; i < res.size(); ++i) {
            if (i) out += SEP;
            out += res[i];
        }
        return out;
    }

    void buildList(TreeNode* node, vector<string>& res) {
        if (!node) {
            res.push_back(NULLT);
            return;
        }
        res.push_back(to_string(node->val));
        buildList(node->left, res);
        buildList(node->right, res);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(const string& data) {
        if (data.empty()) return nullptr;
        vector<string> parts;
        string token;
        stringstream ss(data);
        while (getline(ss, token, ',')) parts.push_back(token);
        deque<string> q(parts.begin(), parts.end());
        return buildTree(q);
    }

private:
    TreeNode* buildTree(deque<string>& q) {
        if (q.empty()) return nullptr;
        string val = q.front(); q.pop_front();
        if (val == NULLT) return nullptr;
        TreeNode* node = new TreeNode(stoi(val));
        node->left = buildTree(q);
        node->right = buildTree(q);
        return node;
    }
};
 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

public class Codec {
    private static final String SEP = ",";
    private static final String NULL = "#";

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        List<String> res = new ArrayList<>();
        buildList(root, res);
        return String.join(SEP, res);
    }

    private void buildList(TreeNode node, List<String> res) {
        if (node == null) {
            res.add(NULL);
            return;
        }
        res.add(String.valueOf(node.val));
        buildList(node.left, res);
        buildList(node.right, res);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.isEmpty()) {
            return null;
        }
        Queue<String> q = new LinkedList<>(Arrays.asList(data.split(SEP)));
        return buildTree(q);
    }

    private TreeNode buildTree(Queue<String> q) {
        String val = q.poll();
        if (val == null || NULL.equals(val)) {
            return null;
        }
        TreeNode node = new TreeNode(Integer.parseInt(val));
        node.left = buildTree(q);
        node.right = buildTree(q);
        return node;
    }
}
 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

class Codec:
    def serialize(self, root: 'TreeNode') -> str:
        res = []
        def dfs(node):
            if not node:
                res.append("#")
                return
            res.append(str(node.val))
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return ",".join(res)

    def deserialize(self, data: str) -> 'TreeNode':
        if not data:
            return None
        
        q = deque(data.split(','))
        
        def build_tree():
            val = q.popleft()
            if val == "#":
                return None
            
            node = TreeNode(int(val))
            node.left = build_tree()
            node.right = build_tree()
            return node
            
        return build_tree()