297. Serialize and Deserialize Binary Tree

Description

See: https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

Note: the format of the string can be of your own choosing, it does not need to be the leet code format.

Solution

I was able to do this on my own! Yay!

I chose to use a serialization format similar to leet code's serialization format. The leetcode format is:

 [1,2,3,null,null,4,5]

Reading the array from left to right builds the tree level by level. In this example:

• level 0: 1

• level 1: 2, 3

• level 2: null, null, 4, 5

Tree of the above input string. Nulls are omitted. Image from leetcode

I chose this format because it seemed easier to use an existing format and validate against it then coming up with my own format.

Code

class Codec:

    TERMINUS = "n"
    def serialize(self, root):
        if not root:
            return ""
        queue = deque()
        queue.append(root)
        result = []
        while queue:
            node = queue.popleft()
            if node:
                result.append(str(node.val))
            else:
                result.append(self.TERMINUS)
                continue
            queue.append(node.left)
            queue.append(node.right)
        return ",".join(result)

    def deserialize(self, data):
        if len(data) <= 0:
            return None
        nodes = data.split(",")
        root = TreeNode(nodes[0])
        queue = deque()
        queue.append(root)
        counter = 1
        while queue:
            node = queue.popleft()
            if nodes[counter] != self.TERMINUS:
                node_left = TreeNode(nodes[counter])
                node.left = node_left
                queue.append(node_left)
            counter += 1
            if nodes[counter] != self.TERMINUS:
                node_right = TreeNode(nodes[counter])
                node.right = node_right
                queue.append(node_right)
            counter += 1
        return root

Serialization

I used BFS traversal to iterate through the tree and build the string. BFS traverses the tree by level which is what I need to build the serialized string.

The code is similar to a standard BFS traversal, but in this case the null children are traversed. This is so the nulls can be included in the output string.

Given the above tree structure, the serialize method will return the following string:

"1,2,3,n,n,4,5,n,n,n,n"

I chose to use 'n' to indicate the null value. The trailing n's are the children of the 4 and 5 nodes. I contemplated stripping them, but did not because it is extra work (another loop). After solving the problem, I looked at other solutions using this method and they did not strip the trailing nulls either.

Time complexity is O(n).

Space complexity is O(n).

Deserialization

Reading the string from left to right will build the tree level by level. After the root node, every two entries will be a left and right child. Using a queue and a counter variable lets us match a parent with its children.

Space complexity is O(n)

Time complexity is O(n)

Deserialization Example

The code uses the following:

• nodes - array based on the data input string, split on commas. For example, the input string will be converted to:

nodes = ["1", "2", "3", "n", "n", "4", "5", "n", "n", "n", "n"]

• queue - a deque containing TreeNodes

• counter - an integer counter for keeping track of the current processing point in the nodes array

At the start the queue contains the root node, TreeNode(1) The counter variable is initialized to 1.

Loop 1

• The root is popped from the queue

• nodes[1] (value 2) and nodes[2] (value 3) are root's left and right children

  • create TreeNodes for both values

  • assign them to root's left and right children

  • put them in the queue

  • queue now contains: [2, 3]

Loop 2

• TreeNode(2) is popped from the queue

• nodes[3] (value n) and nodes[4] (value n) are TreeNode(2)'s left and right children

• Both values are null so do nothing with them

• queue now contains: [3]

Loop 3

• TreeNode(3) is popped from the queue

• nodes[5] (value 4) and nodes[6] (value 5) are TreeNode(3)'s left and right children

  • create TreeNodes for both values

  • assign them to TreeNode(3)'s left and right children

  • put them in the queue

  • queue now contains [4, 5]

Loop 4

• TreeNode(4) is popped from the queue

• nodes[7] (value n) and nodes[8] (value n) are TreeNode(4)'s left and right children

• Both values are null so do nothing with them

• queue now contains: [5]

Loop 5

• TreeNode(5) is popped from the queue

• nodes[9] (value n) and nodes[10] (value n) are TreeNode(5)'s left and right children

• Both values are null so do nothing with them

• queue is now empty, so processing ends

The tree structure has been created.

Other Solutions

Another solution to this problem is to use BFS traversal instead. The following video has a good explanation of how to solve it that way.