Storing recursive results backwards

user_2820289 0
Viewed 50

I am working on this problem that was asked by Google (not to me):

Given the root to a binary tree, implement serialize(root), which serializes the tree into a string, and deserialize(s), which deserializes the string back into the tree.

This is what I have so far, but I cannot seem to make the function serialize store the results (from bottom of the tree and up) into a string. So I'm able to print the results, just not store it...

class Tree:

    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.ser_str = None

    def insert(self, data):
        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Tree(data)
                else:
                    self.left.insert(data)
            elif data >= self.data:
                if self.right is None:
                    self.right = Tree(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

    def serialize(self):
        if self.left:
            self.left.serialize()
        print(self.data)
        if self.right:
            self.right.serialize()

root = Tree(23)
root.insert(10);root.insert(124);root.insert(101);root.insert(1);root.insert(40)
print("here comes the sun")
test = root.serialize()
recursion class python
1 Answers

As noted in comments, the problem with your method is that you just print the data, but never join it to a string and return it. However, that format would also not allow for an unambiguous deserialization of the tree.

If you do not want to use libraries like json, which make this trivial, you could resort to an easily parseable format like Polish Notation, where a + b is written as + a b. In the tree case, the data corresponds to the operator and the left and right branch to the operands.

def serialize(t):
    if t is None:
        return "-"
    else:
        return f"{t.data} {serialize(t.left)} {serialize(t.right)}"
    
def deserialize(s):
    if isinstance(s, str): s = iter(s.split())
    # using an iterator of chunks makes this easier
    d = next(s)
    if d == "-":
        return None
    else:
        return Tree(d, deserialize(s), deserialize(s))

(Note that I made those functions, not methods, and added a few optional parameters to the Tree constructor to make the code simpler.)

When testing with your tree, this serialized the tree to 23 10 1 - - - 124 101 40 - - - -. (I then deserialized the tree and serialized it again and got the same format, so deserialization should work, too.) You can add parens to better see the tree structure in the string: (23 (10 (1 - -) -) (124 (101 (40 - -) -) -)), but the format is unambiguous even without parens.

This basically corresponds to a simple pre-order traversal of the tree, whereas you are doing an in-order traversal, which, like infix-notation a + b, is not unambiguous without parentheses. In-order traversal returns the elements in sorted order, which is nice for some uses, but not here, as it means that differently structured trees holding the same element will serialize to the same sorted list. You could, of course, just add parens, but that will make parsing/deserialization much harder. With parens and in-order, your tree would be (((- 1 -) 10 -) 23 (((- 40 -) 101 -) 124 -)).

(Note: Even if the serialization is ambiguous, you could recreate a binary tree from that, but the form of that tree will be different; in particular, it will be a degenerate binary tree if you just insert the elements in sorted order, as they come out of in your in-order-traversal.)

user_16396250
Related