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 - Preorder(or Postorder) and Inorder Traversal

Intuition

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

Approach

  1. Serialization: Traverse the tree to generate its pre-order and in-order traversal sequences. Concatenate these two sequences into a single string, separated by a special character.
  2. Deserialization: Split the string to get the two traversal sequences back. Use the standard recursive algorithm for building a tree from pre-order and in-order traversals. The first element of the pre-order sequence is the root. Find this root in the in-order sequence; all elements to the left form the left subtree, and all elements to the right form the right subtree. Recursively apply this logic.

Limitations

  1. This approach fails if the tree contains duplicate values, as the mapping from the pre-order root to the in-order sequence becomes ambiguous.
  2. In interview setting, it will be a lot of code to write in 30 minutes

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 2 - 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 3 - 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()

Method 4 - Using Iterative Preorder Traversal

What can be done recursively can also be done iteratively.

 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()