297. Serialize and Deserialize Binary Tree


Problem Description

The problem is about designing an algorithm to perform two complementary tasks: serializing a binary tree to a string and deserializing that string back to the original binary tree structure. Serialization implies converting the tree into a format that can be easily stored or transmitted, while deserialization is the process of reconstructing the tree from the serialized format.

There is flexibility in choosing the method of serialization and deserialization, as long as the serialized string can represent the structure of the tree accurately, and then the tree can be properly restored from this string representation.

It's important to note that the specific format LeetCode uses to represent trees is not mandatory. Developers are encouraged to be creative and design their own serialization/deserialization strategies.

Intuition

For the solution, we can use the well-known tree traversal methods. The chosen traversal method in this solution is preorder traversal, which processes the root before the nodes in the subtrees. This type of traversal assists in maintaining the hierarchy of the tree.

To serialize the tree:

  1. We start with a preorder traversal, visiting nodes in a root-left-right order.
  2. If a node is null, representing the absence of a child in the tree, we store a placeholder (in this case, a hash symbol "#").
  3. Otherwise, we record the value of the node followed by a delimiter (a comma ",") to separate this node's value from the next.
  4. After traversing the entire tree, we combine all the recorded values into a single string.

To deserialize the string back to a tree:

  1. We first split the serialized string by the delimiter "," to get an array of values.
  2. Then we follow the recorded order to reconstruct the tree. We use a recursive helper function that pops values from the array, starting from the first element.
  3. If a value corresponds to the null placeholder, we return None to signify the absence of a node.
  4. Otherwise, we create a new tree node with the current value and set its left and right children by making recursive calls to the helper function.

Since the preorder traversal approach is used, the position of each node is clearly defined by the order in which values appear in the serialized string. This order ensures that each call to the recursive helper function in the deserialization process constructs the correct tree structure.

Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

Solution Approach

The implementation uses the concept of preorder traversal for both serialization and deserialization. Let's break down the approach for each.

Serialization Process:

  1. Preorder traversal recursion: When a node is visited, its value is recorded first, followed by its left and right children recursively.
  2. Handling null nodes: Whenever the traversal encounters a None (e.g., a leaf has no left or right child), it appends a special symbol "#," to denote a null.
  3. Data storage: The values (including null placeholders) are appended to a list, res, during each recursive call.
  4. String conversion: After the traversal is complete, the list of values and placeholders are joined into a single string using ','.join(res), which is then returned as the serialization result.

The preorder traversal is particularly suitable for serialization because it encodes the structure of the tree starting from the root, following a top-down approach that corresponds to how a tree is naturally constructed.

Deserialization Process:

  1. String splitting: The serialized string is split by the delimiter ',' to reconstruct the array of values and null placeholders.
  2. Recursive reconstruction: The deserialization is also recursive, using a nested function inner() that reconstructs the tree by popping the first value from the array of values and using it to construct a TreeNode.
  3. Null nodes handling: If the popped value is the null placeholder, inner() returns None to indicate the absence of a tree node.
  4. Tree node creation: If the value is not the null placeholder, inner() creates a TreeNode with this value, and its left and right children are recursively set by subsequent calls to inner().

By consistently using preorder traversal, the deserialization process can follow the exact sequence of steps that were used to serialize the tree, ensuring that the original tree structure is accurately reconstructed.

Example parse tree for illustration:

Assume the serialization of a tree is "1,2,#,#,3,#,#,". The deserialization process would be:

  • Start with 1: Create a node with value 1.
  • Then move to 2: Create left child of 1 with value 2.
  • Then "#,#": Indicates that 2 has no left or right child, so move back to the parent node 1.
  • Now handle 3: Create right child of 1 with value 3.
  • Finally, "#,#": Indicates that 3 has no left or right child, thus reconstruction is done.

By following this recursive approach, the tree's nodes are constructed in correct preorder, resulting in the tree being restored to its original structure.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Example Walkthrough

Let's consider a simple binary tree as an example to illustrate the serialization and deserialization process. Our binary tree structure will be as follows:

1  1
2 / \
32   3

Serialization:

We will serialize this tree using the serialization process defined above. Here's the step-by-step process:

  1. Preorder traversal recursion: Start at the root node (1). Since it's not null, record its value. Then serialize its left subtree (2), followed by its right subtree (3).
  2. Handling null nodes: As we serialize node 2, we find no left or right children, so we append "#," for each absent child. We do the same for node 3.
  3. Data storage: Throughout the process, we keep appending the values or placeholders to our list res.
  4. String conversion: After we traverse all the nodes, we join all the elements in res with commas to form the serialized string.

Following these steps, the serialization process for our tree will yield the string: "1,2,#,#,3,#,#,".

Deserialization:

Now, we'll take the serialized string "1,2,#,#,3,#,#," and convert it back into the original binary tree using the deserialization process:

  1. String splitting: Split the string by ',' to get an array of values: ["1", "2", "#", "#", "3", "#", "#"].
  2. Recursive reconstruction: Call the nested function inner() which will pop values from the array and construct the tree in preorder.
  3. Null nodes handling: When inner() encounters a "#" (which is the null placeholder), it returns None. This indicates that the current node does not have a left or right child at that position in the tree.
  4. Tree node creation: When inner() pops a numerical value, it creates a TreeNode with that value. It then sets the left child by making a recursive call to inner() (which will process the next value in the array), and the right child by another call to inner() after that.

Deserialization of our serialized string will create the root node 1, create a left child with value 2 (as the next value in the array is "2" and then encounter # placeholders, indicating that 2 has no children), move back to the root node, and then create a right child with value 3 (as the next value in the array is "3"). Following 3, we again encounter # placeholders indicating that 3 also does not have children. With no more elements in the array, the deserialization is complete.

As a result, the original binary tree is reconstructed:

1  1
2 / \
32   3

Throughout this example, you can see that the sequence of values and placeholders in the serialized string directly reflects the structure of the tree, allowing for precise reconstruction during deserialization.

Not Sure What to Study? Take the 2-min Quiz:

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Python Solution

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, x):
4        self.val = x
5        self.left = None
6        self.right = None
7
8class Codec:
9
10    def serialize(self, root):
11        """
12        Encodes a tree to a single string.
13      
14        :param root: TreeNode
15        :return: str
16        """
17        # Handle the base case where the tree is empty.
18        if root is None:
19            return ''
20      
21        # List to store the serialized tree.
22        serialized_values = []
23      
24        # Helper function to perform preorder traversal of the tree and serialize the nodes.
25        def preorder(node):
26            if node is None:
27                # Use '#' to denote a null node.
28                serialized_values.append("#,")
29                return
30            # Serialize the current node's value.
31            serialized_values.append(str(node.val) + ",")
32            # Recursively serialize the left and right subtree.
33            preorder(node.left)
34            preorder(node.right)
35      
36        # Start preorder traversal from the root to serialize the tree.
37        preorder(root)
38        # Join all the serialized values into a single string.
39        return ''.join(serialized_values)
40
41    def deserialize(self, data):
42        """
43        Decodes your encoded data to tree.
44      
45        :param data: str
46        :return: TreeNode
47        """
48        # Handle the case where data is empty, which means the tree is empty.
49        if not data:
50            return None
51      
52        # Split the serialized string by commas to get a list of values.
53        values = data.split(',')
54      
55        # Helper function to build the tree from the list of serialized values.
56        def inner():
57            if values:
58                # Pop the first value from the list, which is the current node's value.
59                first = values.pop(0)
60                if first == '#':
61                    # Return None if the value is a placeholder for a null node.
62                    return None
63                # Create a new TreeNode with the current node's value and recursively build its left and right subtree.
64                return TreeNode(int(first), inner(), inner())
65      
66        # Build the tree from the list of values and return the root.
67        return inner()
68
69# Usage example:
70# codec = Codec()
71# tree = codec.deserialize(codec.serialize(root))
72

Java Solution

1/**
2 * Definition for a binary tree node.
3 */
4class TreeNode {
5    int val;
6    TreeNode left;
7    TreeNode right;
8
9    TreeNode(int x) { 
10        val = x; 
11    }
12}
13
14/**
15 * Codec for encoding and decoding a binary tree into a string representation.
16 */
17public class Codec {
18    // Constants to represent null values and the separator in the serialized string.
19    private static final String NULL_SYMBOL = "#";
20    private static final String SEPARATOR = ",";
21
22    /**
23     * Encodes a tree to a single string.
24     * 
25     * @param root The root of the binary tree.
26     * @return A string representing the pre-order traversal of the binary tree.
27     */
28    public String serialize(TreeNode root) {
29        if (root == null) {
30            return "";
31        }
32        StringBuilder stringBuilder = new StringBuilder();
33        serializePreOrder(root, stringBuilder);
34        return stringBuilder.toString();
35    }
36
37    /**
38     * Helper method to serialize the tree using pre-order traversal.
39     * 
40     * @param node The current node in the tree traversal.
41     * @param stringBuilder The StringBuilder used to create the serialized string.
42     */
43    private void serializePreOrder(TreeNode node, StringBuilder stringBuilder) {
44        if (node == null) {
45            stringBuilder.append(NULL_SYMBOL).append(SEPARATOR);
46            return;
47        }
48        stringBuilder.append(node.val).append(SEPARATOR);
49        serializePreOrder(node.left, stringBuilder);
50        serializePreOrder(node.right, stringBuilder);
51    }
52
53    /**
54     * Decodes your encoded data to tree.
55     * 
56     * @param data The serialized string representation of the binary tree.
57     * @return The root node of the decoded binary tree.
58     */
59    public TreeNode deserialize(String data) {
60        if (data == null || data.isEmpty()) {
61            return null;
62        }
63        List<String> nodesList = new LinkedList<>(Arrays.asList(data.split(SEPARATOR)));
64        return deserializePreOrder(nodesList);
65    }
66
67    /**
68     * Helper method to deserialize the list of values into a binary tree
69     * using pre-order traversal.
70     * 
71     * @param nodesList The linked list of values representing the pre-order traversal.
72     * @return The root node of the (sub)tree.
73     */
74    private TreeNode deserializePreOrder(List<String> nodesList) {
75        String value = nodesList.remove(0);
76        if (NULL_SYMBOL.equals(value)) {
77            return null;
78        }
79        TreeNode node = new TreeNode(Integer.parseInt(value));
80        node.left = deserializePreOrder(nodesList);
81        node.right = deserializePreOrder(nodesList);
82        return node;
83    }
84}
85
86// Example of usage:
87// Codec ser = new Codec();
88// Codec deser = new Codec();
89// TreeNode ans = deser.deserialize(ser.serialize(root));
90

C++ Solution

1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 *     int val;
5 *     TreeNode *left;
6 *     TreeNode *right;
7 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8 * };
9 */
10class Codec {
11public:
12    // Encodes a tree to a single string.
13    string serialize(TreeNode* root) {
14        if (!root) return "";
15        string serializedStr = "";
16        serializePreOrder(root, serializedStr);
17        return serializedStr;
18    }
19
20    // Helper function to serialize a tree using pre-order traversal
21    void serializePreOrder(TreeNode* root, string& serializedStr) {
22        if (!root) {
23            serializedStr += "# "; // Using "#" to denote null node
24        } else {
25            serializedStr += to_string(root->val) + " "; // Add root value
26            serializePreOrder(root->left, serializedStr); // Serialize left subtree
27            serializePreOrder(root->right, serializedStr); // Serialize right subtree
28        }
29    }
30
31    // Decodes your encoded data to tree.
32    TreeNode* deserialize(string data) {
33        if (data.empty()) return nullptr;
34        istringstream dataStream(data);
35        return deserializePreOrder(dataStream);
36    }
37
38    // Helper function to deserialize a stream into a tree using pre-order traversal
39    TreeNode* deserializePreOrder(istringstream& dataStream) {
40        string value;
41        dataStream >> value; // Extract a token
42
43        if (value == "#") return nullptr; // If token is "#", it's a null node
44      
45        TreeNode* root = new TreeNode(stoi(value)); // Create a new node with the extracted value
46        root->left = deserializePreOrder(dataStream); // Deserialize left subtree
47        root->right = deserializePreOrder(dataStream); // Deserialize right subtree
48        return root;
49    }
50};
51
52// Your Codec object will be instantiated and called as such:
53// Codec serializer, deserializer;
54// TreeNode* ans = deserializer.deserialize(serializer.serialize(root));
55

Typescript Solution

1// Definition for a binary tree node.
2class TreeNode {
3    val: number;
4    left: TreeNode | null;
5    right: TreeNode | null;
6  
7    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8        this.val = val === undefined ? 0 : val;
9        this.left = left === undefined ? null : left;
10        this.right = right === undefined ? null : right;
11    }
12}
13
14/**
15 * Encodes a binary tree to a single string representation.
16 *
17 * @param {TreeNode | null} root - The root of the binary tree
18 * @return {string} - The serialized string representation of the tree
19 */
20function serialize(root: TreeNode | null): string {
21    // Empty node is represented by a hash sign
22    if (root === null) {
23        return '#';
24    }
25    // Serialize the current node's value and recurse for the left and right subtrees
26    return `${root.val},${serialize(root.left)},${serialize(root.right)}`;
27}
28
29/**
30 * Decodes the serialized string back to a binary tree.
31 *
32 * @param {string} data - The serialized string to be deserialized
33 * @return {TreeNode | null} - The deserialized binary tree
34 */
35function deserialize(data: string): TreeNode | null {
36    // Split the data by commas and reverse it to prepare for the regeneration of the tree
37    const values = data.split(',').reverse();
38  
39    // A helper function to regenerate the tree from values
40    const buildTree = (): TreeNode | null => {
41        const current = values.pop();
42        // If the current part is a hash or undefined, it represents a null node
43        if (current === undefined || current === '#') {
44            return null;
45        }
46        // Otherwise, create a new TreeNode with the value and recursively build left and right subtrees
47        return new TreeNode(Number(current), buildTree(), buildTree());
48    };
49  
50    // Begin construction of the binary tree from the list of values
51    return buildTree();
52}
53
54// These functions would be called together to serialize a binary tree and then deserialize
55// the string back to a binary tree, ideally resulting in a tree identical to the original.
56// Example test call: deserialize(serialize(root));
57
Fast Track Your Learning with Our Quick Skills Quiz:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Time and Space Complexity

serialize method

Time Complexity:

The time complexity of the serialize method is O(n), where n is the number of nodes in the tree. This is because the method performs a preorder traversal of the tree and processes each node exactly once.

Space Complexity:

The space complexity of the serialize method is O(n) as well. The reason for this is twofold:

  1. The call stack during the recursion of the preorder function will at worst case be O(h) where h is the height of the tree. In the worst case of a skewed tree, h can be n.
  2. The output list res will contain a total of 2n entries (including the # for None nodes), which is linearly proportional to the number of nodes in the tree, hence O(n).

deserialize method

Time Complexity:

The deserialize method also has a time complexity of O(n) because it iterates over each element of the input string once. The inner function is called for every node, meaning it runs n times.

Space Complexity:

The space complexity for the deserialize method is O(n) for the following reasons:

  1. The split operation on the string creates a list of values vals which will be of size n (plus one for the trailing #).
  2. The recursion stack depth of inner() will also be O(h). Just like in serialization, h can be n in the worst case, so space complexity due to recursion can be considered O(n).

Overall, when considering serialization and deserialization together, the time complexity is O(n) and the space complexity is O(n) for both operations.

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫