Python – Serialize & Deserialize Binary Tree (BFS Level‑Order) – Interview DSA Solution 🚀
This solution tackles the Serialize and Deserialize Binary Tree problem using a BFS level‑order traversal approach. The goal is to convert a binary tree into a string representation and rebuild it, preserving its structure.
Key Concepts:
BFS Level‑Order Traversal:
We use a queue to traverse the tree level by level, ensuring that nodes are processed in the order they appear.
Null Markers:
The marker "#" is used to represent null nodes, ensuring that the structure (including missing children) is maintained.
Step‑by‑Step Explanation:
TreeNode Definition:
Similar to the DFS solution, we define a basic TreeNode class.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
#TreeNode #DataStructure
Serialization (BFS):
The serialize method uses a deque to perform level‑order traversal. Each node's value is added to the result list; if a node is null, "#" is appended. The final list is joined into a string.
def serialize(self, root):
if not root:
return ""
q = deque([root])
result = []
while q:
node = q.popleft()
if node:
result.append(str(node.val))
q.append(node.left)
q.append(node.right)
else:
result.append('#')
return ' '.join(result)
#BFS #LevelOrder #Serialization
Deserialization (BFS):
The deserialize method reconstructs the tree from the serialized string. It uses a deque to assign left and right children for each node in a level‑order manner.
def deserialize(self, data):
if not data:
return None
values = data.split()
root = TreeNode(int(values[0]))
q = deque([root])
i = 1
while q:
node = q.popleft()
if values[i] != '#':
node.left = TreeNode(int(values[i]))
q.append(node.left)
i += 1
if values[i] != '#':
node.right = TreeNode(int(values[i]))
q.append(node.right)
i += 1
return root
#BFS #TreeReconstruction #Deserialization
Real‑World Applications:
The BFS approach is useful for encoding trees in a way that preserves their structure exactly, which is critical in network transmissions, file storage, and system design.
Code:
BFS Level‑Order Approach for Serialize & Deserialize Binary Tree
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class CodecBFS:
def serialize(self, root):
if not root:
return ""
q = deque([root])
result = []
while q:
node = q.popleft()
if node:
result.append(str(node.val))
q.append(node.left)
q.append(node.right)
else:
result.append('#')
return ' '.join(result)
def deserialize(self, data):
if not data:
return None
values = data.split()
root = TreeNode(int(values[0]))
q = deque([root])
i = 1
while q:
node = q.popleft()
if values[i] != '#':
node.left = TreeNode(int(values[i]))
q.append(node.left)
i += 1
if values[i] != '#':
node.right = TreeNode(int(values[i]))
q.append(node.right)
i += 1
return root
Example usage:
if _name_ == "__main__":
Constructing a sample tree:
1
/ \
2 3
/ \
4 5
root = TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), TreeNode(5)))
codec_bfs = CodecBFS()
serialized_bfs = codec_bfs.serialize(root)
print("BFS Serialized:", serialized_bfs)
deserialized_root_bfs = codec_bfs.deserialize(serialized_bfs)
(Traverse deserialized_root_bfs to verify correctness)
#SerializeDeserialize #BinaryTree #BFS #LevelOrder #CodingInterview #PythonDSA
On this page of the site you can watch the video online Python – Serialize & Deserialize Binary Tree (BFS Level‑Order) – Interview DSA Solution 🚀 with a duration of hours minute second in good quality, which was uploaded by the user CodeVisium 06 April 2025, share the link with friends and acquaintances, this video has already been watched 1,446 times on youtube and it was liked by 9 viewers. Enjoy your viewing!
