Binary Tree Serialization

Introduction

What is serialization?

"In the context of data storage, serialization is the process of translating data structures or object state into a format that can be stored (for example, in a file or memory buffer, or transmitted across a network connection link) and reconstructed later in the same or another computer environment."

For example, if we want to serialize an array (data structure) [1, 2, 3] we can just store as (string) [1, 2, 3]. If we want to serialize a linked list, 1 -> 2 -> 3, then we can store as 1 -> 2 -> 3. If we want to serialize a hashmap, then we can store as {"key" : "value"}. (doesn't this remind you of json?)

Some applications in practice are XML, JSON, Protocol Buffers, etc.

Question (LC.297)

Design an algorithm to serialize and deserialize a binary tree.

Example

    1
   / \
  2   3
     / \
    4   5
Serialized: [1, 2, 3, null, null, 4, 5]

Analysis

How do we do this for a binary tree? We need to store the nodes in a certain order. What order should we pick We want the ones that the root is easy to identify. Aka preorder and level order (root will be stored first).

Approach 1: BFS (Level Order Traversal)

Serialize

• Step 1 Construct Queue

• Step 2 Convert the queue to string

func serialize(root)
   Step 1 Construct Queue:
   if (root == null) return ""
   ArrayList<TreeNode> queue
   TreeNode current

   queue.enqueue(root)

   // how to get at the right index?
   // so this won't work and queue will never be empty
   // No, No, No we want to store the entire tree from the beginning
   --- ignore ---
   while (!queue.isEmpty) 
       current = queue.get() 
       if (current == null) continue
       queue.enqueue(current.left)
       queue.enqueue(current.right)
   end while
   --- end ignore ---

   // making the move
   for i from 0 to queue.size() - 1
       current = queue.get(i)
       if (current == null) continue
       queue.enqueue(current.left)
       queue.enqueue(current.right)        
   end for

   --- optional ---
   // take out the leaves (nulls) at the lowest level to save space
   while (queue.get(queue.size() - 1) == null)
       queue.dequeue
   end while
   --- end optional ---

   Step 2 Build String :
   StringBuild result
   result.append(queue.get(0).val);
   for i from 1 to queue.size() - 1
       if (queue.get(i) == null)
           result.append("," + "null")
       else
           result.append("," + queue.get(0).val)
   end for

   return result.toString
end func

Deserialize

• BFS on the encoded string

func deserialize(str)
   if (str.equals("")) return null
   String[] nodeValues = str.split(", ")

   Queue<TreeNode> queue
   index = 0
   TreeNode root = new TreeNode(nodeValue[index++])
   queue.enqueue(root)

   while (index < nodeValues.length) // or !queue.isEmpty
       current = queue.dequeue

       if (nodeValues[index] == "null") {
           leftChild = null
       } else {
           leftChild = new TreeNode(nodeValues[index])
           queue.enqueue(leftChild)
       }
       index++
       current.left = leftChild

       if (nodeValues[index] == "null") {
           rightChild = null
       } else {
           rightChild = new TreeNode(nodeValues[index])
           queue.enqueu(rightChild)
       }
       index++
       current.right = rightChild
   end while

   return root
end func

Notes: The goal of this approach is to make the thinking process as straightforward as possible. To be more elegant, we can store nulls[i] for all i to count the number nulls so far at each nodeValue. Then the left child will be values[2 * (i - nulls[i]) + 1] and the right child will be values[2 * (i - nulls[i]) + 2].

Approach 1 Code

public class Codec {
    /**
     * Encodes a tree to a single string
     * Encoding format is (root, root.leftChild, root.rightChild, 
     * leftChild.leftChild, leftChild.rightChild, ...)
     * @param root the root of a binary tree
     * @return the serialization of the given binary tree
     */
    public String serialize(TreeNode root) {
        if (root == null) {
            return "";
        }
        // Step 1 Construct Queue
        // arraylist cause we want to store the entire tree
        ArrayList<TreeNode> queue = new ArrayList<>();
        TreeNode current;
        queue.add(root);

        for (int i = 0; i < queue.size(); i++) {
            current = queue.get(i);
            if (current != null) {
                queue.add(current.left);
                queue.add(current.right);
            }
        }

        // Step 2 Build String
        StringBuilder result = new StringBuilder();
        result.append(queue.get(0).val);
        for (int i = 1; i < queue.size(); i++) {
            result.append(", ");
            if (queue.get(i) == null) {
                result.append("null");
            } else {
                result.append(queue.get(i).val);
            }
        }

        return result.toString();
    }

    /**
     * Decodes the encoded data to a binary tree
     * @param data the serialzed binary tree (an encoded string)
     * @return the root of the restored binary tree
     */
    public TreeNode deserialize(String data) {
        if (data.equals("")) {
            return null;
        }

        String[] values = data.split(", ");
        Queue<TreeNode> queue = new LinkedList<>();
        int index = 0;
        TreeNode root = new TreeNode(Integer.parseInt(values[index++]));
        TreeNode current, leftChild, rightChild;

        queue.offer(root);
        while (index < values.length) { // or while (!queue.isEmpty())
            current = queue.poll();

            if (values[index].equals("null")) {
                leftChild = null;
            } else {
                leftChild = new TreeNode(Integer.parseInt(values[index]));
                queue.offer(leftChild);
            }
            index++;
            current.left = leftChild;

            if (values[index].equals("null")) {
                rightChild = null;
            } else {
                rightChild = new TreeNode(Integer.parseInt(values[index]));
                queue.offer(rightChild);
            }
            index++;
            current.right = rightChild;
        }

        return root;
    }
}

Approach 2: DFS (Pre-order Traversal)

Serialize

• Just a regular preorder traversal

• Use a notebook (called result) to travel around the tree

func serialize(root)
    StringBuilder result
    preorder(root, result)
    return result
end func

func preorder(root, result)
    if (root == null)
        result.append("N ")
    result.append(root.val)
    result.append(" ")
    preorder(root.left, result)
    preorder(root.right, result)
end func

Deserialize

• We want to build this tree top down

• Naturally, the recursive divide and conquer fits this role

func deserialize(encoded_data)
    if (encoded_data == "null") return null
    String[] values = encoded_data.split(" ")
    return preorderDC(values)
end func

int index = 0
func preorderDC(values)
    if (index >= values.length) return null
    if (values[index] == "null") return null
    TreeNode root = new TreeNode(values[index])
    // we don't want to backtrack here
    // we want a permanent change
    // root.left = preorderDC(values, index + 1)
    index++
    root.left = preorderDC(values)
    index++
    root.right = preorderDC(values)
    return root
end func

Approach 2 Code

public class Codec {

    public String serialize(TreeNode root) {
        StringBuilder result = new StringBuilder();
        preorder(root, result);
        return result.substring(0, result.length() - 1);
    }

    private void preorder(TreeNode root, StringBuilder result) {
        if (root == null) {
            result.append("null ");
        } else {
            result.append(root.val);
            result.append(" ");
            preorder(root.left, result);
            preorder(root.right, result);
        }
    }

    public TreeNode deserialize(String data) {
        if (data.equals("null")) {
            return null;
        }
        String[] values = data.split(" ");
        return preorderDC(values); 
    }

    private int index = 0;
    private TreeNode preorderDC(String[] values) {
        // base case
        if (index >= values.length) {
            return null;
        }

        if (values[index].equals("null")) {
            return null;
        }

        // divide and conquer
        TreeNode root = new TreeNode(Integer.parseInt(values[index]));
        index++;
        TreeNode leftSubtree = preorderDC(values);
        index++;
        TreeNode rightSubtree = preorderDC(values);

        // merge
        root.left = leftSubtree;
        root.right = rightSubtree;
        return root;
    }
}

Reference

Wikipedia Serialization