Python Serializing/Deserializing a binary tree

Question

I'm trying to implement a serializing/deserializing algorithm in python for binary trees.

Here's my code:

class Node:
    count = 1
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

    def insert(self, value):
        if self.value > value:
            if self.left is None:
                self.left = Node(value)
                Node.count += 1
            else:
                self.left.insert(value)
        else:
            if self.right is None:
                self.right = Node(value)
                Node.count += 1
            else:
                self.right.insert(value)

# Using preorder
def serialize(root, serial):
    if root != None:
        serial.append(root.value)
        serialize(root.left, serial)
        serialize(root.right, serial)
    else:
        serial.append('x')

def deserialize(newRoot, serial):
    if serial[0] == 'x':
        serial.pop(0)
    else:
        if len(serial) > 0:
            newRoot = Node(serial.pop(0))
            print(newRoot.value)
            deserialize(newRoot.left, serial)
            deserialize(newRoot.right, serial)

print("This program serializes a tree\n")

root = Node(3)
root.insert(1)
root.insert(2)
root.insert(4)
root.insert(5)
root.insert(0)

# Serialize
serial = []
serialize(root, serial)
print(serial)

# Deserialize
newRoot = Node(None)
deserialize(newRoot, serial)
print(newRoot.value)

The problem is, newRoot doesn't get updated by deserialize because python passes it by value. How do I get around this, preferably in the most elegant way? In C/C++, I would just pass a pointer to newRoot and it should get updated accordingly. Thanks!

Return the new root from the function. Instead of def deserialize(newRoot, serial): do def deserialize(serial): ... return newRoot. On the caller side, collect the returned subtrees: newRoot.left=deserialize(serial). — DYZ
– DYZ, Commented Jan 23, 2017 at 22:24

emre. · Accepted Answer · 2017-01-24 11:07:50Z

4

You can return the newly created nodes and assign them as left and right nodes. Also poping the first element of a list is more costly than poping the last element, so reverseing the list at the beginning and then using it in the recursion will be more performant in your case. So the code will become something like:

def deserialize(serial):
    serial.reverse()
    return _deserialize(serial)

def _deserialize(serial):
    if not serial:
        return None

    node = None
    value = serial.pop()
    if value != 'x':
        node = Node(value)
        node.left = _deserialize(serial)
        node.right = _deserialize(serial)
    return node

root = deserialize(serial)
print(root.value)

edited Jan 24, 2017 at 11:07

answered Jan 23, 2017 at 22:38

emre.

1,29611 silver badges13 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Rakesh R · Accepted Answer · 2021-03-13 17:48:29Z

You can create left and right subtree within deserialize function and return the root. Here is my code:

node_list = []
MARKER = -1
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
    
def serialize(root):
    if root is None:
        node_list.append(MARKER)
        return

    node_list.append(root.val)
    serialize(root.left)
    serialize(root.right)

def deserialize(root, node_list):
    if node_list:
        val = node_list.pop(0)
    else:
        return
    
    if val == MARKER:
        return

    # Create root, left and right recursively
    root = Node(val)
    root.left = deserialize(root.left, node_list)
    root.right = deserialize(root.right, node_list)
    return root

def inorder_traversal(root):
    if root:
        inorder_traversal(root.left)
        print(root.val, end=' ')
        inorder_traversal(root.right)

if __name__=="__main__":
    # Create tree
    root = Node(20)
    root.left = Node(8)
    root.right = Node(22)
    root.left.left = Node(4)
    root.left.right = Node(12)
    root.left.right.left = Node(10)
    root.left.right.right = Node(14)

    print("Inorder traversal before serialization..")
    inorder_traversal(root)
    print('')

    # serialize the tree and insert elements into a list
    serialize(root)
    print(node_list)

    root1 = None
    root1 = deserialize(root1, node_list)
    print("Inorder traversal after deserialization..")
    inorder_traversal(root1)
    print('')

Collectives™ on Stack Overflow

Python Serializing/Deserializing a binary tree

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related