Serialize and deserialize binary search tree

Question

Is there any good advice on how to improve performance in terms of algorithm time complexity? I am using a recursive solution and am not sure if any faster non-recursive solution exists.

import sys
class TreeNode:
    def __init__(self, value, left, right):
        self.value = value
        self.left = left
        self.right = right
    def serialize_tree(self, result):
        result.append(self.value)
        if self.left:
            self.left.serialize_tree(result)
        if self.right:
            self.right.serialize_tree(result)
    def print_tree(self, result):
        result.append(self.value)
        if self.left:
            self.left.print_tree(result)
        else:
            result.append('#')
        if self.right:
            self.right.print_tree(result)
        else:
            result.append('#')
    @staticmethod
    def deserialize_tree(source):
        if len(source) == 1:
            return TreeNode(source[0], None, None)
        cur = TreeNode(source[0], None, None)
        for i,v in enumerate(source):
            if i == 0:
                root_value = v
                continue
            if v > root_value:
                break
        if v > root_value:
            cur.right = TreeNode.deserialize_tree(source[i:])
        if v > root_value and i - 1 > 0:
            cur.left = TreeNode.deserialize_tree(source[1:i])
        if not (v > root_value) and i == len(source) - 1:
            cur.left = TreeNode.deserialize_tree(source[1:i+1])

        return cur

if __name__ == "__main__":
    #   5
    #  3 6
    # 2   7
    root = TreeNode(5, TreeNode(3, TreeNode(2, None, None), None), TreeNode(6, None, TreeNode(7, None, None)))
    result = []
    root.serialize_tree(result)
    print result
    new_root = TreeNode.deserialize_tree(result)
    result2 = []
    new_root.print_tree(result2)
    print result2

Answer 1

serialize_tree is fine. deserialize_tree is \$O(n^2)\$ . In the case of balanced tree, it's still \$O(n\log{n})\$. To prove that to yourself, just add a counter inside deserialize_tree, or measure the runtime, vs input size.

But here's why:

• First, you scan the serialized result to find the split between the left and the right tree. This takes linear time \$O(n)\$ if the tree is size \$n\$. To fix this you need to change the algorithm.
• Then, you call source[1:i] and source[i:]. These take \$O(n)\$ time together--taking a slice is linear time in python. To fix this, you just need to pass around start and end indices.
• Finally, you do the above a number of times equal to the height of the tree, which in the best case is \$\log n\$ layers, in the worst case \$n\$ layers.

The reason you are running into this problem is that you can't deserialize recursively with your serialization format. Replace deserialize_tree by print_tree instead--you need a placeholder for an empty subtree for it to work. Here are corrected methods (not actually tested):

@staticmethod
def _deserialize_one_subtree(source, start_position):
    """
    Returns a deserialized subtree, from a stream of elements. A subtree may or may not be the whole stream.
    Returns (subtree, new_position)
    """
    if source[start_position] == '#':
        return None, start_position + 1
    else:
        root, position = source[start_position], start_position + 1
        left, position = _deserialize_one_subtree(source, position)
        right, position = _deserialize_one_subtree(source, position)
        return TreeNode(root, left, right), position
@staticmethod
def deserialize_tree(source):
    """Deserialize a binary tree"""
    tree, end_position = _deserialize_one_subtree(source, 0)
    assert end_position == len(source)
    return tree