Binary tree deserialization

In this code deserialization method does not work properly my code link:


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 import Callable
from typing import Generic, Optional, TypeVar

Element = TypeVar("Element")

class BinaryNode(Generic[Element]):

  def __init__(
    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:
    if self.right_child:

  def traverse_pre_order(self, visit: Callable[[Element], None]) -> None:
    if hasattr(self, 'left_child') and self.left_child:
    if hasattr(self, 'right_child') and self.right_child:

  def traverse_post_order(self, visit: Callable[[Element], None]) -> None:
    if self.left_child:
    if self.right_child:

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


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)))
    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)
deserialized_tree = deserialize(array)

# 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.