Serialization means transforming tree structure to a linear structure to store it. Generally, traversal is used to implement serialization. So, what kinds of traversal could be used to implement serialization? We mainly focus on binary tree in this article. At the end of the article we will discuss a little about N-ary tree.

1 Serialization with null

In order to use only one traversal, we must store the null nodes. The result of serializing is not compact. Preorder traversal, postorder traversal and level order traversal could implement serialization with storing the null node. The inorder traversal doesn’t work.

Preorder traversal with null

//preorder with null
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        helper(root, sb);
        String res = sb.toString();
        return res.substring(0, res.length() - 1);
    }
    public void helper(TreeNode root, StringBuilder sb)
    {
        if(root == null)
        {
            sb.append("#,");
        }
        else
        {
            sb.append(root.val + ",");
            helper(root.left, sb);
            helper(root.right, sb);
        }
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.length()==0) return null;
        String[] dataArray=data.split(",");
        return dehelper(dataArray, new int[]{0});
    }
    public TreeNode dehelper(String[] dataArray, int[] cur)
    {
        if(dataArray[cur[0]].equals("#"))
        {
            cur[0]++;
            return null;
        }
        else
        {
            TreeNode root = new TreeNode(Integer.valueOf(dataArray[cur[0]]));
            cur[0]++;
            root.left = dehelper(dataArray, cur);
            root.right = dehelper(dataArray, cur);
            return root;
        }
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

Postorder traversal with null

//postorder with null
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        helper(root, sb);
        String res = sb.toString();
        return res.substring(0,res.length()-1);
    }
    public void helper(TreeNode root, StringBuilder sb)
    {
        if(root==null)
        {
            sb.append("null,");
        }
        else
        {
            helper(root.left, sb);
            helper(root.right, sb);
            sb.append(root.val + ",");
        }
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.length()==0) return null;
        String[] dataArray=data.split(",");
        return dehelper(dataArray, new int[]{dataArray.length - 1});
    }
    public TreeNode dehelper(String[] dataArray, int[] cur)
    {
        if(dataArray[cur[0]].equals("null"))
        {
            cur[0]--;
            return null;
        }
        else
        {
            TreeNode root = new TreeNode(Integer.valueOf(dataArray[cur[0]]));
            cur[0]--;
            root.right = dehelper(dataArray, cur);
            root.left = dehelper(dataArray, cur);
            return root;
        }
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

Level order traversal with null

//level order with null
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) return "";
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.offer(root);
        TreeNode temp;
        while(q.size() > 0)
        {
            temp = q.poll();
            if(temp == null) sb.append("#,");
            else
            {
                sb.append(temp.val + ",");
                q.offer(temp.left);
                q.offer(temp.right);
            }
        }
        String res = sb.toString();
        return res.substring(0, res.length() - 1);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.length() == 0) return null;
        String[] dataArray = data.split(",");
        Queue<TreeNode> q = new LinkedList<>();
        for(int i = 0; i < dataArray.length; i++)
        {
            if(dataArray[i].equals("#"))
            {
                q.offer(null);
            }
            else
            {
                q.offer(new TreeNode(Integer.valueOf(dataArray[i])));
            }
        }
        return buildTree(q);
    }
    
    private TreeNode buildTree(Queue<TreeNode> q)
    {
        Queue<TreeNode> processed = new LinkedList<>();
        processed.offer(q.poll());
        TreeNode root = processed.peek();
        if(root == null) return null;
        while(!processed.isEmpty())
        {
            TreeNode parent = processed.poll();
            TreeNode left = q.poll();
            TreeNode right = q.poll();
            if(left != null)
            {
                processed.offer(left);
            }
            if(right != null)
            {
                processed.offer(right);
            }
            parent.left = left;
            parent.right = right;
        }
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

2 Serialization without null

If null nodes are not stored in the serialization result, which means the result is compact, then other conditions must be satisfied.

First, we must also have preorder traversal, postorder traversal or level order traversal. Then we have to know the inorder traversal. Or the binary tree must be a binary search tree. Because for a binary tree, if we sort one of other traversals, we could get the inorder traversal. They are equivalent. Here we just focus on the BST’s serialization.

Preorder for BST

//Preorder
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) return "";
        StringBuilder sb = new StringBuilder();
        helper(root, sb);
        String res = sb.toString();
        return res.substring(0, res.length() - 1);
    }
    public void helper(TreeNode root, StringBuilder sb)
    {
        if(root != null)
        {
            sb.append(root.val + ",");
            helper(root.left, sb);
            helper(root.right, sb);
        }
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == "") return null;
        data = data + "," + "#";
        String[] dataArray = data.split(",");
        return dehelper(dataArray, new int[]{0}, "#");
    }
    
    public TreeNode dehelper(String[] dataArray, int[] cur, String stop)
    {
        if(dataArray[cur[0]].equals("#") || !stop.equals("#") && Integer.valueOf(dataArray[cur[0]]) >= Integer.valueOf(stop))
        {
            return null;
        }
        TreeNode root = new TreeNode(Integer.valueOf(dataArray[cur[0]]));
        cur[0]++;
        root.left = dehelper(dataArray, cur, root.val + "");
        root.right = dehelper(dataArray, cur, stop);
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

Postorder for BST

//Postorder
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) return "";
        StringBuilder sb = new StringBuilder();
        helper(root, sb);
        String res = sb.toString();
        return res.substring(0, res.length() - 1);
    }
    public void helper(TreeNode root, StringBuilder sb)
    {
        if(root != null)
        {
            helper(root.left, sb);
            helper(root.right, sb);
            sb.append(root.val + ",");
        }
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == "") return null;
        data = "#," + data;
        String[] dataArray = data.split(",");
        return dehelper(dataArray, new int[]{dataArray.length - 1}, "#");
    }
    
    public TreeNode dehelper(String[] dataArray, int[] cur, String stop)
    {
        if(dataArray[cur[0]].equals("#") || !stop.equals("#") && Integer.valueOf(dataArray[cur[0]]) <= Integer.valueOf(stop))
        {
            return null;
        }
        TreeNode root = new TreeNode(Integer.valueOf(dataArray[cur[0]]));
        cur[0]--;
        root.right = dehelper(dataArray, cur, root.val + "");
        root.left = dehelper(dataArray, cur, stop);
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

Level order for BST

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    class NodeWrap{
        TreeNode node;
        Integer min;
        Integer max;
        public NodeWrap(TreeNode node, Integer min, Integer max)
        {
            this.node = node;
            this.min = min;
            this.max = max;
        }
    }

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) return "";
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        TreeNode temp;
        while(q.size() > 0)
        {
            temp = q.poll();
            sb.append(temp.val + ",");
            if(temp.left != null)
                q.offer(temp.left);
            if(temp.right != null)
                q.offer(temp.right);
        }
        String res = sb.toString();
        return res.substring(0, res.length() - 1);
    }
    
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == "") return null;
        String[] dataArray = data.split(",");
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0; i < dataArray.length; i++)
        {
            q.offer(Integer.valueOf(dataArray[i]));
        }
        return buildTree(q);
    }
    
    public TreeNode buildTree(Queue<Integer> q)
    {
        TreeNode root = new TreeNode(q.poll());
        Queue<NodeWrap> limit = new LinkedList<>();
        limit.offer(new NodeWrap(root, null, null));
        while(q.size() > 0)
        {
            NodeWrap nw = limit.poll();
            TreeNode n = nw.node;
            if((nw.min == null || q.peek() > nw.min) && q.peek() < nw.node.val)
            {
                n.left = new TreeNode(q.poll());
                limit.offer(new NodeWrap(n.left, nw.min, n.val));
            }
            if(q.size() == 0) break;
            if((nw.max == null || q.peek() < nw.max) && q.peek() > nw.node.val)
            {
                n.right = new TreeNode(q.poll());
                limit.offer(new NodeWrap(n.right, n.val, nw.max));
            }            
        }
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

3 Serialization for N-ary Tree

We only implement the preorder traversal and postorder traversal with null.

Preorder with null

//Preorder
/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val,List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Codec {

    // Encodes a tree to a single string.
    public String serialize(Node root) {
        if(root == null) return "";
        StringBuilder sb = new StringBuilder();
        helper(root, sb);
        String res = sb.toString();
        return res.substring(0, res.length() - 1);
    }
    
    public void helper(Node root, StringBuilder sb)
    {
        if(root != null)
        {
            sb.append(root.val + ",");
            for(int i = 0; i < root.children.size(); i++)
            {
                helper(root.children.get(i), sb);
            }
            sb.append("#,");
        }
    }

    // Decodes your encoded data to tree.
    public Node deserialize(String data) {
        if(data.length() == 0) return null;
        String[] dataArray = data.split(",");
        return dehelper(dataArray, new int[]{0});
    }
    
    public Node dehelper(String[] dataArray, int[] cur)
    {
        if(dataArray[cur[0]].equals("#"))
        {
            
            cur[0]++;
            return null;
        }
        else
        {
            List<Node> children = new ArrayList<>();
            int rootval = Integer.valueOf(dataArray[cur[0]]);
            cur[0]++;
            while(cur[0] < dataArray.length)
            {
                Node temp = dehelper(dataArray, cur);
                if(temp != null) children.add(temp);
                else break;
            }
            return new Node(rootval, children);
        }
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

Postorder with null

//Postorder
/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val,List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/
class Codec {

    // Encodes a tree to a single string.
    public String serialize(Node root) {
        if(root == null) return "";
        StringBuilder sb = new StringBuilder();
        helper(root, sb);
        String res = sb.toString();
        return res.substring(0, res.length() - 1);
    }
    
    public void helper(Node root, StringBuilder sb)
    {
        if(root != null)
        {
            sb.append("#,");
            for(int i = 0; i < root.children.size(); i++)
            {
                helper(root.children.get(i), sb);
            }
            sb.append(root.val + ",");
        }
    }

    // Decodes your encoded data to tree.
    public Node deserialize(String data) {
        if(data.length() == 0) return null;
        String[] dataArray = data.split(",");
        return dehelper(dataArray, new int[]{dataArray.length - 1});
    }
    
    public Node dehelper(String[] dataArray, int[] cur)
    {
        if(dataArray[cur[0]].equals("#"))
        {
            
            cur[0]--;
            return null;
        }
        else
        {
            LinkedList<Node> children = new LinkedList<>();
            int rootval = Integer.valueOf(dataArray[cur[0]]);
            cur[0]--;
            while(cur[0] >= 0)
            {
                Node temp = dehelper(dataArray, cur);
                if(temp != null) children.addFirst(temp);
                else break;
            }
            return new Node(rootval, children);
        }
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

Reference

[1] https://zhuanlan.zhihu.com/p/26418233

Leave a Reply

Your email address will not be published. Required fields are marked *