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:
- We start with a preorder traversal, visiting nodes in a root-left-right order.
- If a node is null, representing the absence of a child in the tree, we store a placeholder (in this case, a hash symbol
"#"). - Otherwise, we record the value of the node followed by a delimiter (a comma
",") to separate this node's value from the next. - After traversing the entire tree, we combine all the recorded values into a single string.
To deserialize the string back to a tree:
- We first split the serialized string by the delimiter
","to get an array of values. - 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.
- If a value corresponds to the null placeholder, we return
Noneto signify the absence of a node. - 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.
What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?
1def fun(arr: List[int]) -> List[int]:
2 import heapq
3 heapq.heapify(arr)
4 res = []
5 for i in range(3):
6 res.append(heapq.heappop(arr))
7 return res
81public static int[] fun(int[] arr) {
2 int[] res = new int[3];
3 PriorityQueue<Integer> heap = new PriorityQueue<>();
4 for (int i = 0; i < arr.length; i++) {
5 heap.add(arr[i]);
6 }
7 for (int i = 0; i < 3; i++) {
8 res[i] = heap.poll();
9 }
10 return res;
11}
121class HeapItem {
2 constructor(item, priority = item) {
3 this.item = item;
4 this.priority = priority;
5 }
6}
7
8class MinHeap {
9 constructor() {
10 this.heap = [];
11 }
12
13 push(node) {
14 // insert the new node at the end of the heap array
15 this.heap.push(node);
16 // find the correct position for the new node
17 this.bubble_up();
18 }
19
20 bubble_up() {
21 let index = this.heap.length - 1;
22
23 while (index > 0) {
24 const element = this.heap[index];
25 const parentIndex = Math.floor((index - 1) / 2);
26 const parent = this.heap[parentIndex];
27
28 if (parent.priority <= element.priority) break;
29 // if the parent is bigger than the child then swap the parent and child
30 this.heap[index] = parent;
31 this.heap[parentIndex] = element;
32 index = parentIndex;
33 }
34 }
35
36 pop() {
37 const min = this.heap[0];
38 this.heap[0] = this.heap[this.size() - 1];
39 this.heap.pop();
40 this.bubble_down();
41 return min;
42 }
43
44 bubble_down() {
45 let index = 0;
46 let min = index;
47 const n = this.heap.length;
48
49 while (index < n) {
50 const left = 2 * index + 1;
51 const right = left + 1;
52
53 if (left < n && this.heap[left].priority < this.heap[min].priority) {
54 min = left;
55 }
56 if (right < n && this.heap[right].priority < this.heap[min].priority) {
57 min = right;
58 }
59 if (min === index) break;
60 [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61 index = min;
62 }
63 }
64
65 peek() {
66 return this.heap[0];
67 }
68
69 size() {
70 return this.heap.length;
71 }
72}
73
74function fun(arr) {
75 const heap = new MinHeap();
76 for (const x of arr) {
77 heap.push(new HeapItem(x));
78 }
79 const res = [];
80 for (let i = 0; i < 3; i++) {
81 res.push(heap.pop().item);
82 }
83 return res;
84}
85Solution Approach
The implementation uses the concept of preorder traversal for both serialization and deserialization. Let's break down the approach for each.
Serialization Process:
- Preorder traversal recursion: When a node is visited, its value is recorded first, followed by its left and right children recursively.
- 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 anull. - Data storage: The values (including null placeholders) are appended to a list,
res, during each recursive call. - 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:
- String splitting: The serialized string is split by the delimiter
','to reconstruct the array of values and null placeholders. - 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 aTreeNode. - Null nodes handling: If the popped value is the null placeholder,
inner()returnsNoneto indicate the absence of a tree node. - Tree node creation: If the value is not the null placeholder,
inner()creates aTreeNodewith this value, and its left and right children are recursively set by subsequent calls toinner().
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 value1. - Then move to
2: Create left child of1with value2. - Then
"#,#": Indicates that2has no left or right child, so move back to the parent node1. - Now handle
3: Create right child of1with value3. - Finally,
"#,#": Indicates that3has 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.
What's the output of running the following function using the following tree as input?
1def serialize(root):
2 res = []
3 def dfs(root):
4 if not root:
5 res.append('x')
6 return
7 res.append(root.val)
8 dfs(root.left)
9 dfs(root.right)
10 dfs(root)
11 return ' '.join(res)
121import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4 StringJoiner res = new StringJoiner(" ");
5 serializeDFS(root, res);
6 return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10 if (root == null) {
11 result.add("x");
12 return;
13 }
14 result.add(Integer.toString(root.val));
15 serializeDFS(root.left, result);
16 serializeDFS(root.right, result);
17}
181function serialize(root) {
2 let res = [];
3 serialize_dfs(root, res);
4 return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8 if (!root) {
9 res.push("x");
10 return;
11 }
12 res.push(root.val);
13 serialize_dfs(root.left, res);
14 serialize_dfs(root.right, res);
15}
16Example 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:
- 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).
- 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. - Data storage: Throughout the process, we keep appending the values or placeholders to our list
res. - String conversion: After we traverse all the nodes, we join all the elements in
reswith 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:
- String splitting: Split the string by
','to get an array of values:["1", "2", "#", "#", "3", "#", "#"]. - Recursive reconstruction: Call the nested function
inner()which will pop values from the array and construct the tree in preorder. - Null nodes handling: When
inner()encounters a"#"(which is the null placeholder), it returnsNone. This indicates that the current node does not have a left or right child at that position in the tree. - Tree node creation: When
inner()pops a numerical value, it creates aTreeNodewith that value. It then sets the left child by making a recursive call toinner()(which will process the next value in the array), and the right child by another call toinner()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.
Solution Implementation
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))
721/**
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));
901/**
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));
551// 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));
57Breadth first search can be used to find the shortest path between two nodes in a directed graph.
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:
- The call stack during the recursion of the
preorderfunction will at worst case beO(h)wherehis the height of the tree. In the worst case of a skewed tree,hcan ben. - The output list
reswill contain a total of2nentries (including the#forNonenodes), which is linearly proportional to the number of nodes in the tree, henceO(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:
- The split operation on the string creates a list of values
valswhich will be of sizen(plus one for the trailing#). - The recursion stack depth of
inner()will also beO(h). Just like in serialization,hcan benin the worst case, so space complexity due to recursion can be consideredO(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 using problem constraints.
What are the most two important steps in writing a depth first search function? (Select 2)
Recommended Readings
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
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
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.