LeetCode 297. Serialize and Deserialize Binary Tree

October 08, 2020

LeetCode serializes binary trees as a succinct breadth-first iteration. You can read more about succinct encodings of binary trees and the algorithm we're using here.

We can't be much more space efficient than LeetCode's default. None is an object in Python, but, at 16 bytes, it's smaller than Python ints, bools, etc. We would use a bit array but Python doesn't have anything like that. Using an integer and bit manipulation would save a lot of space, but make it hard to read the data in reverse order when we deserialize.

The serialize and deserialize steps are $O(n)$ in time and space complexity.

import collections
import math
import unittest

from .. import TreeNode

class Test(unittest.TestCase):

    def setUp(self):
        self.s = Codec()

    def test_examples(self):
        t = TreeNode.from_list([1,2,3,None,None,4,5])
        self.assertEqual(t, self.s.deserialize(self.s.serialize(t)))
        t = TreeNode.from_list([])
        self.assertEqual(t, self.s.deserialize(self.s.serialize(t)))
        t = TreeNode.from_list([1])
        self.assertEqual(t, self.s.deserialize(self.s.serialize(t)))
        t = TreeNode.from_list([1,2])
        self.assertEqual(t, self.s.deserialize(self.s.serialize(t)))

    def test_right(self):
        t = TreeNode.from_list([3,None,2])
        self.assertEqual(t, self.s.deserialize(self.s.serialize(t)))
        t = TreeNode.from_list([3,None,2,None,None,None,1,None,None,None,None,None,None,None,7])
        self.assertEqual(t, self.s.deserialize(self.s.serialize(t)))

    def test_left(self):
        t = TreeNode.from_list([3,2,None])
        self.assertEqual(t, self.s.deserialize(self.s.serialize(t)))
        t = TreeNode.from_list([3,2,None,1,None,None,None,7,None,None,None,None,None,None,None])
        self.assertEqual(t, self.s.deserialize(self.s.serialize(t)))

class Codec:

    def encode_succinct(self, node, q):
        if not node:
            q.append(None)
            return
        q.append(node.val)
        self.encode_succinct(node.left, q)
        self.encode_succinct(node.right, q)

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        q = collections.deque()
        self.encode_succinct(root, q)
        return q

    def decode_succinct(self, q):
        b = q.popleft()
        if b == None:
            return None
        n = TreeNode(b)
        n.left = self.decode_succinct(q)
        n.right = self.decode_succinct(q)
        return n

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        return self.decode_succinct(data)