449. Serialize and Deserialize BST

MediumTreeDepth-First SearchBreadth-First SearchDesignBinary Search TreeStringBinary Tree
Leetcode Link

Problem Description

Serialization refers to the process of converting a data structure or object into a sequence of bits, allowing it to be stored on a disk, held in memory, or sent over a network connection. The ultimate goal is to be able to recover or reconstruct the original data structure from the sequence of bits. In this problem, we have to devise a method that can serialize a binary search tree (BST) into a string and deserialize that string back to the original BST. The binary search tree is a data structure where the left child of a node contains a key less than or equal to its parent node, and the right child contains a key greater than the parent node. One of the critical requirements for this serialization/deserialization algorithm is that the resultant encoded string should be as compact as possible.

Intuition

To serialize a binary search tree, we can use a depth-first traversal approach (pre-order, in-order, or post-order). However, to ensure that the encoded string is compact, we don't necessarily need to include information about the 'null' children as we would in a typical binary tree serialization. This is because the properties of a BST allow us to reconstruct the tree without this extra information.

For the solution provided, pre-order traversal (root, left, right) is used during serialization. By visiting the root node first, it ensures that we have the information about parent nodes before we try to reconstruct children nodes during deserialization. This serialization results in a string of space-separated integer values representing node values in the order they were visited.

For deserialization, given the series of values and knowing the value of the parent, we can determine which of the subsequent numbers form the left subtree (all those less than or equal to the parent's value) and which form the right subtree (all those greater than the parent's value). We can use a recursive approach to reconstruct the tree by maintaining a range of valid values for each node during the reconstruction process (dfs). We start with the first value as the root of the tree and maintain index i to keep track of the current position in the serialized string. We continue to construct the tree by invoking recursive calls that bound valid nodes for the left subtree with a maximum value (parent's value) and for the right subtree with a minimum value (parent's value). This follows the BST invariant where left subtrees contain values less than the root and right subtrees contain values greater than it.

The recursive dfs function keeps track of the allowable range for each subtree as (mi, mx) and updates the range as it goes down each level. It places each subsequent value in its rightful position in the tree according to BST rules, and halts when there is no number within the range of allowable values (avoiding insertion of an invalid number into the BST).

The chosen deserialization method is efficient in that it doesn't require us to recreate each subtree fully before connecting it to its parent, and the compact serialization format omits redundant 'null' indicators.

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

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

In a binary min heap, the minimum element can be found in:

Solution Approach

The solution approach involves two primary functions: serialize for converting the binary search tree to a string and deserialize for reconstructing the tree from the string.

Serialization (serialize function)

  1. The serialize function traverses the BST using a Depth-First Search (DFS). The traversal is a pre-order traversal where the node is processed before its children.
  2. It defines an inner function dfs(root) that performs the recursive traversal.
  3. Starting at the root, each time dfs is called on a node, it appends the node's value to an external list called nums.
  4. The left and right children are visited recursively, with the base case being when a None (indicating an absence of a node) is encountered, at which point the function returns without doing anything. This step omits the need to encode None values.
  5. The serialize function returns a string made by joining the values in nums with a space as a delimiter.

Deserialization (deserialize function)

  1. deserialize begins by converting the input string back into a list of integers (nums) using split and map functions.
  2. It then defines a recursive function dfs(mi, mx) that will create a node from nums[i] if the value is within the specified range (mi, mx), and correctly place it within the tree structure.
  3. A pointer i is used to track the current index in the list nums as nodes are created.
  4. For each node, the dfs function calls itself twice: once for creating the left child with an updated range mi to node's value (ensuring values are less than the parent for the left subtree), and once for creating the right child with an updated range from node's value to mx (ensuring values are greater for the right subtree).
  5. It continues to build the tree by advancing i appropriately and returning None when an index is out of range or a value is not within the valid interval. This effectively places each value at the correct node in the BST.
  6. The deserialization process starts by calling dfs with an initial range of negative to positive infinity, representing that any value can be the root of the tree. From there, the appropriate ranges are enforced for each subtree.
  7. Finally, deserialize returns the root of the reconstructed tree.

Both serialization and deserialization use the fundamental properties of a binary search tree: the left nodes are less than the parent, and the right nodes are greater. This makes the pre-order serialization compact, as no 'null' indicators are needed, and enables the reconstruction without additional information.

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

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Example Walkthrough

Let us walk through a small example to illustrate the solution approach.

Consider the following binary search tree:

1    5
2   / \
3  3   7
4 / \   \
52   4   8

Serialization Example

Using the serialize function with a pre-order traversal, the process would be as follows:

  1. Start at the root node (5).
  2. Append '5' to the nums list.
  3. Go to the left child (3), and repeat the process:
    • Append '3' to the nums list.
    • Go to the left child (2), append '2' to the nums list. Since '2' does not have children, go back up.
    • Go to the right child (4), append '4' to the nums list. With no children, return to node '3'.
  4. Since all nodes under '3' have been processed, return to node '5'.
  5. Now, go to the right child of '5' which is '7':
    • Append '7' to the nums list.
    • '7' has no left child, so we consider the right child.
    • Go to the right child (8), append '8' to the nums list. Since '8' does not have children, go back up.
  6. There are no more nodes to visit. The traversal is complete.

The resulting nums list is [5, 3, 2, 4, 7, 8]. The serialize function joins these values to create the string "5 3 2 4 7 8".

Deserialization Example

Now, using the deserialize function, we will reconstruct a binary search tree from the string "5 3 2 4 7 8":

  1. Convert the string into a list of numbers: [5, 3, 2, 4, 7, 8].
  2. Start the dfs function with the range (-โˆž, โˆž).
  3. The first value is 5, which falls within the range, so it becomes the root.
  4. Call dfs for the left subtree with range (-โˆž, 5). The next number is 3, which is within the range and becomes the left child of 5.
  5. Again call dfs for the left subtree, now with range (-โˆž, 3). Number 2 fits and becomes the left child of 3.
  6. Attempt to call dfs again for a left child of 2, but the next number 4 does not fit the (-โˆž, 2) range. Therefore, 2 has no left child.
  7. Call dfs for the right child of 2 with the range (2, 3). The number 4 fits the range and becomes the right child of 3.
  8. For 4, thereโ€™s no left or right child meeting the respective ranges, so it remains a leaf node.
  9. Return to the root's right subtree, with range (5, โˆž). The next number is 7, which becomes the right child of 5.
  10. 7 does not have a left child within the (5, 7) range.
  11. Repeat dfs for the right child of 7, with range (7, โˆž). Number 8 is within the range and becomes the right child of 7.

After completing the process, we would reconstruct the original binary search tree structure:

1    5
2   / \
3  3   7
4 / \   \
52   4   8

This example illustrates how the solution approach systematically traverses the BST for serialization and uses the properties of BST to rebuild the tree from the serialized string during deserialization.

Solution Implementation

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, value):
4        self.val = value
5        self.left = None
6        self.right = None
7
8class Codec:
9    def serialize(self, root):
10        """Encodes a tree to a single string.
11      
12        We perform a preorder traversal of the binary tree and record the values.
13        The 'None' situation (meaning no child) is implicitly handled by not recording anything.
14        """
15
16        def preorder_traversal(node):
17            """Recursive helper function for preorder traversal."""
18            if node is None:
19                return
20            values.append(node.val)
21            preorder_traversal(node.left)
22            preorder_traversal(node.right)
23
24        values = []
25        preorder_traversal(root)
26        return " ".join(map(str, values))
27
28    def deserialize(self, data):
29        """Decodes your encoded data to tree.
30      
31        Constructs the tree from preorder traversal values within the min-max range.
32        This makes use of the property of binary search trees (BST)
33        where left subtree nodes are less than root, and right subtree nodes are greater.
34        """
35      
36        def construct_tree(min_val, max_val):
37            """Recursive helper function to construct tree with the min-max constraint.
38          
39            The function updates the index 'i' implicitly as it forms the tree
40            by moving through the encoded string.
41            """
42            nonlocal index
43            # Base case: When the index has covered all elements or
44            # the current value is out of the [min_val, max_val] range.
45            if index == len(values) or not (min_val <= values[index] <= max_val):
46                return None
47          
48            # Create the root node with the current value.
49            root_value = values[index]
50            node = TreeNode(root_value)
51            index += 1
52          
53            # Construct left and right subtrees recursively.
54            node.left = construct_tree(min_val, root_value)
55            node.right = construct_tree(root_value, max_val)
56            return node
57
58        values = list(map(int, data.split()))
59        index = 0
60        return construct_tree(float('-inf'), float('inf'))
61
62
63# The Codec class usage example
64# codec = Codec()
65# tree_encoding = codec.serialize(root)
66# tree_decoding = codec.deserialize(tree_encoding)
67# Now, tree_decoding is the root of your binary tree.
68
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
14public class Codec {
15  
16    private int index; // Instead of 'i', use 'index' for clarification
17    private List<String> nodeValues; // Use 'nodeValues' instead of 'nums' for clarity
18    private static final int INFINITY = 1 << 30; // Use static final for constants with a clear name
19
20    // Encodes a tree to a single string.
21    public String serialize(TreeNode root) {
22        nodeValues = new ArrayList<>();
23        preOrderDfs(root); // Use meaningful naming for the DFS method
24        return String.join(" ", nodeValues);
25    }
26
27    // Decodes your encoded data to tree.
28    public TreeNode deserialize(String data) {
29        if (data == null || data.isEmpty()) {
30            return null;
31        }
32        index = 0;
33        nodeValues = Arrays.asList(data.split(" "));
34        return deserializeHelper(-INFINITY, INFINITY); // Use a helper method with clear limits for the node values
35    }
36
37    // Helper method: performs pre-order DFS traversal to serialize the tree.
38    private void preOrderDfs(TreeNode node) {
39        if (node == null) {
40            return;
41        }
42        nodeValues.add(String.valueOf(node.val));
43        preOrderDfs(node.left);
44        preOrderDfs(node.right);
45    }
46
47    // Helper method: uses DFS logic to deserialize the list of node values into a tree.
48    private TreeNode deserializeHelper(int minValue, int maxValue) {
49        if (index == nodeValues.size()) {
50            return null;
51        }
52        int value = Integer.parseInt(nodeValues.get(index));
53        // Ensure that the current value falls within the specified min and max bounds
54        if (value < minValue || value > maxValue) {
55            return null;
56        }
57        TreeNode node = new TreeNode(value);
58        index++;
59        node.left = deserializeHelper(minValue, value); // Set the current value as the new upper limit for the left subtree
60        node.right = deserializeHelper(value, maxValue); // ... and as the new lower limit for the right subtree
61        return node;
62    }
63}
64
65// Usage example:
66// Codec serializer = new Codec();
67// Codec deserializer = new Codec();
68// String serializedTree = serializer.serialize(root);
69// TreeNode rootNode = deserializer.deserialize(serializedTree);
70
1/**
2 * Definition for a binary tree node.
3 */
4struct TreeNode {
5    int val;
6    TreeNode *left;
7    TreeNode *right;
8
9    TreeNode(int value) : val(value), left(nullptr), right(nullptr) {}
10};
11
12/**
13 * Codec class is responsible for serializing and deserializing a binary tree into/from a string.
14 */
15class Codec {
16public:
17    // Encodes a tree to a single string.
18    string serialize(TreeNode* root) {
19        // Handling edge case where the tree is empty.
20        if (!root) {
21            return "";
22        }
23      
24        // Use a string to store serialized data.
25        string serialized = "";
26      
27        // Define a lambda function to perform pre-order traversal and build the serialized data.
28        function<void(TreeNode*)> preorderTraverse = [&](TreeNode* node) {
29            if (!node) {
30                return;
31            }
32          
33            // Append current node value to serialized data followed by a space.
34            serialized += to_string(node->val) + " ";
35          
36            // Recurse left
37            preorderTraverse(node->left);
38          
39            // Recurse right
40            preorderTraverse(node->right);
41        };
42      
43        // Perform serialization using predefined lambda function.
44        preorderTraverse(root);
45      
46        // Remove trailing space from the serialized string.
47        serialized.pop_back();
48      
49        return serialized;
50    }
51
52    // Decodes your encoded data to tree.
53    TreeNode* deserialize(string data) {
54        // Handling edge case where the given data string is empty.
55        if (data.empty()) {
56            return nullptr;
57        }
58      
59        // Split the input string by space and convert each part into integer.
60        vector<int> values = split(data, ' ');
61        int index = 0;
62      
63        // Define a lambda function to recursively build the tree from serialized data.
64        function<TreeNode*(int, int)> constructTree = [&](int minValue, int maxValue) -> TreeNode* {
65            if (index == values.size() || values[index] < minValue || values[index] > maxValue) {
66                return nullptr;
67            }
68          
69            int currentValue = values[index++];
70            TreeNode* node = new TreeNode(currentValue);
71          
72            // Build the left subtree considering the current value as maximum allowed value.
73            node->left = constructTree(minValue, currentValue);
74          
75            // Build the right subtree considering the current value as minimum allowed value.
76            node->right = constructTree(currentValue, maxValue);
77          
78            return node;
79        };
80      
81        // Construct and return the root of the binary tree.
82        return constructTree(INT_MIN, INT_MAX);
83    }
84
85    // Utility method to split the given string 's' around a delimiter 'delim' and return integer tokens.
86    vector<int> split(const string& s, char delim) {
87        vector<int> tokens;
88        stringstream ss(s);
89        string token;
90      
91        // Iterate over the stream and split the string into tokens.
92        while (getline(ss, token, delim)) {
93            tokens.push_back(stoi(token)); // Convert each token to an integer and add to the tokens vector.
94        }
95        return tokens;
96    }
97};
98
99// Example of usage:
100// Codec* serializer = new Codec();
101// Codec* deserializer = new Codec();
102// string serializedTree = serializer->serialize(root);
103// TreeNode* deserializedRoot = deserializer->deserialize(serializedTree);
104// Ensure to clean up allocated memory resources appropriately.
105
1// Definition for a binary tree node.
2interface TreeNode {
3    val: number;
4    left: TreeNode | null;
5    right: TreeNode | null;
6}
7
8// Function to create a new TreeNode instance.
9const createTreeNode = (value: number): TreeNode => ({
10    val: value,
11    left: null,
12    right: null
13});
14
15// Function to encode a tree to a single string.
16const serialize = (root: TreeNode | null): string => {
17    if (!root) {
18        return "";
19    }
20    let serialized = "";
21
22    const preorderTraverse = (node: TreeNode | null): void => {
23        if (node === null) {
24            return;
25        }
26        serialized += `${node.val} `;
27        preorderTraverse(node.left);
28        preorderTraverse(node.right);
29    };
30
31    preorderTraverse(root);
32    return serialized.trim(); // Removing the trailing space.
33};
34
35// Function to decode your encoded data to tree.
36const deserialize = (data: string): TreeNode | null => {
37    if (data.length === 0) {
38        return null;
39    }
40
41    const values: number[] = split(data, ' ');
42    let index = 0;
43
44    const constructTree = (minValue: number, maxValue: number): TreeNode | null => {
45        if (index === values.length || values[index] < minValue || values[index] > maxValue) {
46            return null;
47        }
48
49        const currentValue = values[index++];
50        const node = createTreeNode(currentValue);
51
52        node.left = constructTree(minValue, currentValue);
53        node.right = constructTree(currentValue, maxValue);
54
55        return node;
56    };
57
58    return constructTree(Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER);
59};
60
61// Utility function to split a string 's' by a delimiter 'delim' and returns an array of numbers.
62const split = (s: string, delim: string): number[] => {
63    return s.split(delim).map(str => parseInt(str, 10));
64};
65
66// Example usage:
67// const serializedTree: string = serialize(root);
68// const deserializedRoot: TreeNode | null = deserialize(serializedTree);
69
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which of the following problems can be solved with backtracking (select multiple)

Time and Space Complexity

Serialize Function:

  • Time Complexity: The serialize function performs a Depth-First Search (DFS) on the tree. It visits each node exactly once. Therefore, the time complexity is O(n), where n is the number of nodes in the tree.

  • Space Complexity: The space complexity for the serialize function is O(n) as well, due to the storage required for the nums list, which contains n elements in the worst case. Additionally, because the recursive calls add frames to the call stack, in the worst case of an unbalanced tree, the stack space required can also be O(n). Therefore, the total space complexity is O(n).

Deserialize Function:

  • Time Complexity: The deserialize function recursively reconstructs the binary tree. The function dfs is called once for each element in the nums list, resulting in a time complexity of O(n), where n is the number of elements, which corresponds to the number of tree nodes.

  • Space Complexity: Space complexity for the deserialize function is also O(n). The nums list requires O(n) space. The recursion stack may also consume up to O(n) space in the worst case, where the tree is completely unbalanced (e.g., a linked list). The use of inf does not affect space complexity.

In conclusion, the time complexity and space complexity for both serialize and deserialize functions are O(n).

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

Fast Track Your Learning with Our Quick Skills Quiz:

What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

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 ๐Ÿ‘จโ€๐Ÿซ