297. Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

My accepted code can be found here

This problem required to implement two functions, both the serialize and deserialize, it’s a basic parser problem at first glance, and I solve the problem as it actually is, the performance is not quite good compared to other’s.

The serialize generate the integer sequence by preorder traversal, and mark null pointer as '.', simple as that, the algorithm is as follow:

serialize(node: Node): string:
    if node is null:
        return "."
    return join([string(node.value), serialize(node.left), serialize(node.right)], ',')

The problem requires that both algorithm cannot use local object state, so the parser comes a little tedious, since we have to pass back the parsed index of the string

deserialize(tree: string): Node:
    return deserialize'(tree, 0)[0]

deserialize'(tree: string, index: int): (Node, int):
    if tree[index] == ',':
        index = index + 1
    if tree[index] == '.':
        return (null, index + 1)
    let (value, index') = parseValue(tree, index)
    let (left, index'') = deserialize'(tree, index')
    let (right, index''') = deserialize'(tree, index'')
    return (Node(value, left, right), index''')

// parses tree value start with specific index
// returns the value and next index of the value
parseValue(str: string, index: int): (Value, int):
    // ...

The time complexity are both linear with respect to the size of the input.

Hooray! Semester End

So this is probably the last of algorithm homework weekly, next week is for exam.