In this code deserialization method does not work properly my code link:
https://replit.com/@murtaza63/binary-Tree-serilize-and-deserilize#main.py
Hi,
To deserialize you should use the same function as for the serialization (traverse_pre_order).
In my solution I initialized the children of BinaryNode in any case, strengthened a few conditions and implemented a ‘Visit’ function for the deserialization.
The solution works, surely there is a simpler way to fix it.
from __future__ import annotations
from collections.abc import Callable
from typing import Generic, Optional, TypeVar
Element = TypeVar("Element")
class BinaryNode(Generic[Element]):
def __init__(
self,
value: Element,
left: Optional[BinaryNode[Element]] = None,
right: Optional[BinaryNode[Element]] = None,
):
self.value: Element = value
if value:
self.left_child: Optional[BinaryNode[Element]] = BinaryNode(left)
self.right_child: Optional[BinaryNode[Element]] = BinaryNode(right)
def __str__(self) -> str:
return self.diagram_for_node(self)
def diagram_for_node(self,
node: Optional[BinaryNode],
top: str = "",
root: str = "",
bottom: str = "") -> str:
if not node:
return root + "None\n"
if node.value is None and not hasattr(node, 'left_child') and not hasattr(node, 'right_child') is None:
return root + f"{node.value}\n"
return (self.diagram_for_node(node.right_child, top + " ", top + "┌──",
top + "│ ") +
root + f"{node.value}\n" + self.diagram_for_node(
node.left_child, bottom + "│ ", bottom + "└──", bottom + " "))
def traverse_in_order(self, visit: Callable[[Element], None]) -> None:
if self.left_child:
self.left_child.traverse_in_order(visit)
visit(self.value)
if self.right_child:
self.right_child.traverse_in_order(visit)
def traverse_pre_order(self, visit: Callable[[Element], None]) -> None:
visit(self.value)
if hasattr(self, 'left_child') and self.left_child:
self.left_child.traverse_pre_order(visit)
else:
visit(None)
if hasattr(self, 'right_child') and self.right_child:
self.right_child.traverse_pre_order(visit)
else:
visit(None)
def traverse_post_order(self, visit: Callable[[Element], None]) -> None:
if self.left_child:
self.left_child.traverse_post_order(visit)
if self.right_child:
self.right_child.traverse_post_order(visit)
visit(self.value)
T = TypeVar("T")
"""
## #2. Serialization
A common task in software development is serializing an object into another
data type. This process is known as serialization, and allows custom types to
be used in systems that only support a closed set of data types.
An example of serialization is JSON. Your task is to devise a way to serialize
a binary tree into an array, and a way to deserialize the array back into
the same binary tree.
To clarify this problem, consider the following binary tree:
![Binary Tree](binary-tree.png)
A particular algorithm may output the serialization as
`[15, 10, 5, None, None, 12, None, None, 25, 17, None, None, None]`.
The deserialization process should transform the array back into the same
binary tree. Note that there are many ways to perform serialization.
You may choose any way you wish.
"""
root = BinaryNode(value=15)
ten = BinaryNode(value=10)
five = BinaryNode(value=5)
twelve = BinaryNode(value=12)
twenty_five = BinaryNode(value=25)
seventeen = BinaryNode(value=17)
root.left_child = ten
root.right_child = twenty_five
ten.left_child = five
ten.right_child = twelve
twenty_five.left_child = seventeen
tree = root
print(tree)
def serialize(node: BinaryNode) -> list[Optional[T]]:
array: list[Optional[T]] = []
node.traverse_pre_order(lambda x: array.append(x))
return array
def setNode(array, value):
if value and array:
return BinaryNode(array.pop(0), left=BinaryNode(array.pop(0), left=array.pop(0), right=array.pop(0)), right=BinaryNode(array.pop(0), left=array.pop(0), right=array.pop(0)))
else:
return None
def deserialize(array: list[Optional[T]]) -> Optional[BinaryNode]:
if not array:
return None
root = BinaryNode(value=array.pop(0), left=array.pop(0), right=array.pop(0))
root.traverse_pre_order(lambda x: setNode(array, x))
# node.left_child = deserialize(array)
# node.right_child = deserialize(array)
return root
array = serialize(tree)
print(array)
deserialized_tree = deserialize(array)
print(deserialized_tree)
# TODO Fix Bug: This does not work correctly
# assert str(tree) == str(deserialized_tree)
Note: the print doesn’t show the real content of the tree yet
This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.