General Tree serialize, desirialize

code: python

from collections import deque

class Node:

def __init__(self, name):

self.right = None

self.left = None

self.name = name

class GeneralTree:

# n: number of node

# O(n), O(n)

def serialize(self, root):

if not root:

return "#"

return f"{root.name},{self.serialize(root.left)},{self.serialize(root.right)}"

# O(n), O(n)

def deserialize(self, data):

def deserialize_helper(queue):

name = queue.popleft()

if name == "#":

return None

node = Node(name)

node.left = deserialize_helper(queue)

node.right = deserialize_helper(queue)

return node

queue = deque(data.split(","))

return deserialize_helper(queue)

import pytest

@pytest.fixture

def sample_tree():

a = Node("A")

b = Node("B")

c = Node("C")

d = Node("D")

a.left = b

a.right = c

c.right = d

return a

# A

# / \

# B C

# \

# D

def test_serialize(sample_tree):

gt = GeneralTree()

serialized = gt.serialize(sample_tree)

expected = "A,B,#,#,C,#,D,#,#"

assert serialized == expected

def test_deserialize():

gt = GeneralTree()

data = "A,B,#,#,C,#,D,#,#"

deserialized = gt.deserialize(data)

assert deserialized.name == "A"

assert deserialized.left.name == "B"

assert deserialized.right.name == "C"

assert deserialized.right.right.name == "D"