\

Serialize And Deserialize Binary Tree

Difficulty: N/A | Solved: December 20, 2025

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.

Example 1:

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

Example 2:

Input: root = [] Output: []

Brainstorming

Optimal Solution

That’s a perfect place to start. If the problem statement itself is fuzzy, we need to clarify it before we can solve anything.

“What does converting to a string mean?”

Imagine you have a complex object in your computer’s memory, like a binary tree. It’s made of nodes, and each node has pointers (.left, .right) that point to other nodes’ memory addresses.

# In Memory (Conceptual)
Node_A (at memory address 0x1000) -> left: 0x2000, right: 0x3000
Node_B (at memory address 0x2000) -> left: None, right: None
Node_C (at memory address 0x3000) -> left: None, right: None

You cannot just save 0x1000, 0x2000, 0x3000 to a file. Why?

  1. If you close your program and re-open it, the operating system might give you completely different memory addresses.
  2. If you send that file to another computer, its memory layout is totally different. The address 0x1000 is meaningless over there.

Serialisation means creating a universal, self-contained representation of the tree’s structure and values that is independent of memory addresses. A string is the most common way to do this.

The Goal: You need to invent a “language” or “format” to describe your tree. Then, you need to write a translator (serialize) that converts your in-memory tree into a string in that language, and another translator (deserialize) that can read a string in your language and perfectly rebuild the original in-memory tree.

Example Analogy: Building a Lego Model

  • The In-memory Tree: The fully built, 3D Lego model.
  • The serialize function: The person who writes the instruction manual. They look at the model and write down a step-by-step string: "Take a red 2x4 brick; place it at the base. Take a blue 2x2 brick; place it on top of the red one to the left..."
  • The String: The instruction manual itself. It’s just text. You can save it, email it, etc.
  • The deserialize function: A person who reads the instruction manual (the string) and, without ever having seen the original model, can build an identical copy.

Let’s Brainstorm a “Language” for a Tree.

How can we describe this tree as a string?

      1
     / \
    2   3

  • Idea 1 (Simple but flawed): Just list the nodes. "1,2,3".

    • Problem: If you deserialize this, how do you know 2 is the left child and 3 is the right? This string could also represent a tree where 3 is the left child and 2 is the right. We lost the structural information.

  • Idea 2 (Better): We need to represent the structure. Tree traversals are a great way to visit nodes in a specific order. Let’s try a pre-order traversal.

    • Root -> Left -> Right
    • The preorder traversal of this tree is 1, 2, 3. Still the same ambiguous string.

  • Idea 3 (The Key Insight): We need to also record when a path ends. We need a marker for None children.

    • Let’s use "#" as our None marker.
    • Let’s do a pre-order traversal again, but this time, if we encounter a None child, we record a "#".

Let’s trace this for our tree:

  1. Visit root 1. String is now "1,".
  2. Go left to 2.
    • Visit 2. String is now "1,2,".
    • Go left from 2. It’s None. String is now "1,2,#,".
    • Go right from 2. It’s None. String is now "1,2,#,#,".
  3. Go right from 1 to 3.
    • Visit 3. String is now "1,2,#,#,3,".
    • Go left from 3. It’s None. String is now "1,2,#,#,3,#,".
    • Go right from 3. It’s None. String is now "1,2,#,#,3,#,#,".

Our serialized string is "1,2,#,#,3,#,#". This string is not ambiguous. It contains all the information needed to rebuild the exact original tree.

(Prompt):

  1. Based on this “preorder traversal with markers for None” idea, can you write the pseudocode for the serialize(root) function? It will likely be a recursive helper function.
  2. Now for the harder part: think about deserialize. You have the string "1,2,#,#,3,#,#". How can you read this from left to right to rebuild the tree? (Hint: The process will also be recursive).

okay so now its clear , basically we want the information in a string format that can be used to to construct the tree again. since string is again an immutable type we would need to define it as a global list element

serialize_string = [""]
#... add details
curr_string = serialize_string[0]
curr_string += result # whatever it is None represented as #  or the value

# actual implemention below 
class TreeNode:
	def __init__(self, val=None, left=None, right=None):
		self.val = val
		self.left = left
		self.right = right

def serialize(root: TreeNode):
	serialize_string = [""]
	
	def serialize_helper(node:TreeNode):
		# Base case
		if node is None:
			serialize_string[0] += "#"
		
		# Recursive step pre order root->left->right
		serialize_string[0] += f"{root.val}"
		serialize_helper(root.left)
		serialize_helper(root.right)
	
	serialize_helper(root)
	
	return serialize_string[0]

for constructing the result i think preorder itself will not be enough

lets assume the above code gives us "1,2,#,#,3,#,#" when we go about re constructing it we will know that the first element of the string is the root and the next element will be the left node of this root no i think we can do this we can assume that till the time we don’t hit # in the remaining string that the elements will always be the left element of the current root if we hit # it means we should stop going left and come back

 deserailization in progress

   1 get root make the tree node
  / go left with the current tree node with the remainig string
 2 get root make it a tree node attach is to the global tree
 / go left with the current tree node
 # there is nothing more to the left return to root i.e 2 and go right

so we need a way to pass the global tree and attach current nodes whenever they are valid do this in preorder style root->left->right and the base case is if the current zero index is # in the string string just return


# actual implemention below 
class TreeNode:
	def __init__(self, val=None, left=None, right=None):
		self.val = val
		self.left = left
		self.right = right

def deserialize(serialized_string: str):
	# edge case
	if serialized_string[0] == "#":
		return None
	
	def deserialize_helper(serialized_string):
		# base case
		if serialized_string[0] == "#":
			return 
		
		# recursive step
		root_val = serialized_string[0]
		current_root = TreeNode(root_val)
		remaining_string = serialized_string[1:]
		current_root.left = deserialize_helper(remaining_string)
		current_root.right = deserialize_helper(remaining_string)
		
		return current_root
		
    binary_tree = deserialize_helper(serialized_string)
    
    return binary_tree
  • 🍅 (pomodoro::WORK) (duration:: 30m) (begin:: 2025-12-17 10:49) - (end:: 2025-12-17 11:19)

Critique of serialise

Your approach will work, but it has some bugs and can be made cleaner.

  1. State Management: serialize_string = [""] and modifying [0] works, but it’s a bit clunky. A simpler way is to have the recursive helper return the string for its subtree, and then combine the results at the caller.
  2. Base Case vs. Recursive Step:
   if node is None:
       serialize_string[0] += "#" # Missing a comma/delimiter
   
   # This part runs even if node is None, which will crash
   serialize_string[0] += f"{root.val}" 
   serialize_helper(root.left)
   ```

You need an if/else block. If node is None, you do one thing. If it's not None, you do the pre-order traversal.

```python
def serialize_helper(node):
   if node is None:
   	return "#,"
   
   # root str
   root_str = str(node.val) + ","
   root_left_str = serialize_helper(node.left)
   root_right_str = serialize_helper(node.right)
   
   return root_str + root_left_str + root_right_str

Critique of deserialise (You’re so close!)

Your logic is nearly perfect.

“we can assume that till the time we don’t hit # in the remaining string that the elements will always be the left element of the current root”

This is the key. The preorder string is a stream of data. The call that is building the left subtree will consume some part of this stream, and whatever is left is for the right subtree.

The Problem with Your Code:
You pass remaining_string to both recursive calls.

remaining_string = serialized_string[1:]
current_root.left = deserialize_helper(remaining_string)
current_root.right = deserialize_helper(remaining_string) # Problem!

The deserialize_helper for the right child starts reading from the same remaining_string as the left child did, instead of starting from where the left child finished.

The Solution: How to “Consume” the String?

The easiest way to handle this is to turn the string into a list or a queue, so that when a recursive call processes an element, it’s permanently “consumed” for all other calls.

Let’s convert the string “1,2,#,#,3,#,#” into a list data = ["1", "2", "#", "#", "3", "#", "#"].

Revised Logic for deserialize_helper(data_list):

  1. Get the next element: val = data_list.pop(0) (removes the first element).

  2. Base Case: If val is “#”, you’ve hit a None node. Return None.

  3. Recursive Step:

    • If val is a number, create the root = TreeNode(int(val)).
    • Build Left: The next elements in the list belong to the left subtree. Recursively call the helper to build it.
      root.left = deserialize_helper(data_list)
    • Build Right: After the root.left call has completely finished (it has consumed all the elements it needs from the list), the next elements in the (now shorter) list belong to the right subtree.
      root.right = deserialize_helper(data_list)
    • Return the root you built.

This structure works because the data_list is a shared, mutable object. When deserialize_helper for the left child pops elements, they are gone for good, and the deserialize_helper for the right child automatically starts reading from the correct position.

class TreeNode:
	def __init__(self, val=None, left=None, right=None):
		self.val = val
		self.left = left
		self.right = right

def deserialize_helper(serialized_string:str):
	data_list = serialized_string.split(",")
	
	def deserialized_helper(data_list):
		val = data_list.pop(0)
		if val == "#":
			return None
		
		root = TreeNode(int(val))
		root.left = deserialized_helper(data_list)
		root.right = deserialized_helper(data_list)
		
		return root
	
	
	tree = deserialized_helper(data_list)
	
	return tree
  • 🥤 (pomodoro::BREAK) (duration:: 15m) (begin:: 2025-12-17 11:21) - (end:: 2025-12-17 12:03)

Final solution


class TreeNode:
	def __init__(self, val=None, left=None, right=None):
		self.val = val
		self.left = left
		self.right = right
		


class codec:
	
	def __init__(self):
		pass
	
	def _serialize_helper(self, node):
		if node is None:
			return "#,"
		
		# Pre-order: Root, Left, Right
		root_str = str(node.val) + ","
		root_left_str = self._serialize_helper(node.left)
		root_right_str = self._serialize_helper(node.right)
		
		return root_str + root_left_str + root_right_str
	
	def _deserialize_helper(self, data_list:list[str]):
		val = data_list.pop(0)
		if val == "#":
			return None
		# Recursive Step: # 1. Create the current node.
		root = TreeNode(int(val))
		# 2. Build the left subtree. The recursive call will consume # all necessary tokens from the front of the shared data_list.
		root.left = self._deserialize_helper(data_list)
		# 3. Build the right subtree. This call automatically starts # from where the left subtree's construction finished.
		root.right = self._deserialize_helper(data_list)
		
		return root

	def serialize(self, root:TreeNode):
		serialized_string = self._serialize_helper(root)
		return serialized_string
	
	def deserialize(self, serialized_string:str):
		data_list = serialized_string.split(",")
		tree = self._deserialize_helper(data_list)
		return tree