Python – Serialize & Deserialize Binary Tree (BFS Level‑Order) – Interview DSA Solution 🚀

Veröffentlicht am: 06 April 2025
auf dem Kanal: CodeVisium

1,446

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

Auf dieser Seite können Sie das Online-Video Python – Serialize & Deserialize Binary Tree (BFS Level‑Order) – Interview DSA Solution 🚀 mit der Dauer stunde minuten sekunde in guter Qualität ansehen, das der Benutzer CodeVisium 06 April 2025 hochgeladen hat, den Link mit Freunden und Bekannten teilen, dieses Video wurde auf Youtube bereits 1,446 Mal angesehen und es wurde von 9 den Zuschauern gefallen. Viel Spaß beim Betrachtenden Zuschauern gefallen!

3,763