Skip to content
AI360Xpert
Back to Trees
Hard

Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment. Design an algorithm to serialize and deserialize a binary tree.

Examples

Input:root = [1,2,3,null,null,4,5]
Output:[1,2,3,null,null,4,5]
Input:root = []
Output:[]

Constraints

  • The number of nodes in the tree is in the range [0, 10^4].
  • -1000 <= Node.val <= 1000

Approach

To serialize, perform a preorder DFS traversal. Record node values separated by commas. Record null nodes as "N". To deserialize, split the string by commas to get an array of values. Use an iterator or index pointer. Perform the same preorder DFS traversal, reading values from the array one by one. If the value is "N", return null. Otherwise, create a node, and recursively call deserialize for the left and right children.

Complexity Analysis

Time Complexity
O(n)
Space Complexity
O(n)

This uses preorder traversal.

Solution.java
public class Codec {
    // Encodes a tree to a single string.    public String serialize(TreeNode root) {        List<String> res = new ArrayList<>();        serializeDFS(root, res);        return String.join(",", res);    }        private void serializeDFS(TreeNode node, List<String> res) {        if (node == null) {            res.add("N");            return;        }        res.add(String.valueOf(node.val));        serializeDFS(node.left, res);        serializeDFS(node.right, res);    }
    // Decodes your encoded data to tree.    public TreeNode deserialize(String data) {        String[] vals = data.split(",");        int[] index = {0}; // Use array to act as mutable pointer        return deserializeDFS(vals, index);    }        private TreeNode deserializeDFS(String[] vals, int[] i) {        if (vals[i[0]].equals("N")) {            i[0]++;            return null;        }                TreeNode node = new TreeNode(Integer.parseInt(vals[i[0]]));        i[0]++;                node.left = deserializeDFS(vals, i);        node.right = deserializeDFS(vals, i);        return node;    }}