Solution For Serialize And Deserialize Binary Tree
The problem of Serialize And Deserialize Binary Tree on leetcode is to design an algorithm to serialize and deserialize a 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. Deserialization is the reverse process, converting the bit sequence back into the original data structure.
To solve this problem, we can use a recursive approach.
- Serialization
In serialization, we need to traverse the binary tree and store its nodes in a string. We can use any traversal technique for this purpose. Here, we are using preorder traversal.
In preorder traversal, we first visit the root, then the left subtree, and then the right subtree. We can store the tree nodes in a string by appending the node values to the string with a delimiter.
Algorithm:
1. Create an empty string.
2. Traverse the tree recursively in preorder.
3. If the current node is null, append a ‘#’ character to the string and return.
4. Append the value of the current node followed by a delimiter to the string.
5. Recursively call the function for the left subtree and then the right subtree.
Code:
class Codec:
def serialize(self, root):
if not root:
return "#"
str_list = []
str_list.append(str(root.val))
str_list.append(self.serialize(root.left))
str_list.append(self.serialize(root.right))
return "|".join(str_list)
- Deserialization
In deserialization, we need to take the string we got from the serialization function and reconstruct the binary tree. We can use a similar recursive approach to do this.
Algorithm:
1. Split the string using the delimiter.
2. If the current element is ‘#’, return None.
3. Create a new node with the value of the current element.
4. Recursively call the function for the left subtree and then the right subtree.
5. Return the root node of the binary tree.
Code:
“`
class Codec:
def deserialize(self, data):
node_list = data.split(“|”)
root = self.buildTree(node_list)
return root
def buildTree(self, node_list):
val = node_list.pop(0)
if val == "#":
return None
node = TreeNode(int(val))
node.left = self.buildTree(node_list)
node.right = self.buildTree(node_list)
return node
“`
To test the solution, we can create a binary tree, serialize it, and then deserialize it to get the original binary tree back.
Code:
“`
Creating a binary tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.right.left = TreeNode(4)
root.right.right = TreeNode(5)
Creating an instance of Codec
codec = Codec()
Serializing the binary tree
serialized_tree = codec.serialize(root)
print(“Serialized tree:”, serialized_tree)
Deserializing the binary tree
deserialized_tree = codec.deserialize(serialized_tree)
Testing if the deserialized tree is same as the original tree
assert root.val == deserialized_tree.val
assert root.left.val == deserialized_tree.left.val
assert root.right.val == deserialized_tree.right.val
assert root.right.left.val == deserialized_tree.right.left.val
assert root.right.right.val == deserialized_tree.right.right.val
“`
Step by Step Implementation For Serialize And Deserialize Binary Tree
/** * 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) { // Base case if (root == null){ return ""; } // Recursive case StringBuilder sb = new StringBuilder(); sb.append(root.val + ","); sb.append(serialize(root.left)); sb.append(serialize(root.right)); return sb.toString(); } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { // Base case if (data == null || data.length() == 0){ return null; } // Recursive case String[] vals = data.split(","); TreeNode root = new TreeNode(Integer.parseInt(vals[0])); Queuequeue = new LinkedList<>(); queue.add(root); int i = 1; while (!queue.isEmpty()){ TreeNode curr = queue.poll(); if (!vals[i].equals("")){ curr.left = new TreeNode(Integer.parseInt(vals[i])); queue.add(curr.left); } i++; if (!vals[i].equals("")){ curr.right = new TreeNode(Integer.parseInt(vals[i])); queue.add(curr.right); } i++; } return root; } } // Your Codec object will be instantiated and called as such: // Codec codec = new Codec(); // codec.deserialize(codec.serialize(root));
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Codec: def serialize(self, root): """Encodes a tree to a single string. :type root: TreeNode :rtype: str """ # base case if not root: return "X" # preorder traversal left = self.serialize(root.left) right = self.serialize(root.right) return str(root.val) + "," + left + "," + right def deserialize(self, data): """Decodes your encoded data to tree. :type data: str :rtype: TreeNode """ def dfs(): val = next(vals) if val == "X": return None node = TreeNode(int(val)) node.left = dfs() node.right = dfs() return node # use a generator to iterate over data vals = iter(data.split(",")) return dfs() # Your Codec object will be instantiated and called as such: # codec = Codec() # codec.deserialize(codec.serialize(root))
//Serialize function serialize(root) { //Check for empty tree if(root === null) { return ""; } //Create an array to store the tree nodes let arr = []; //Push the root node into the array arr.push(root); //Loop through the array while it's not empty while(arr.length) { //Get the first node in the array let node = arr.shift(); //Check if the node is null if(node === null) { //If the node is null, add "null" to the array arr.push("null"); } else { //If the node is not null, add the node's value to the array arr.push(node.val); //Push the node's left and right child into the array arr.push(node.left); arr.push(node.right); } } //Return the array as a string return arr.toString(); } //Deserialize function deserialize(data) { //Check for empty string if(data === "") { return null; } //Split the string into an array let arr = data.split(","); //Create a queue let queue = []; //Get the first value in the array (the root node) let root = new TreeNode(arr.shift()); //Push the root node into the queue queue.push(root); //Loop through the array while(arr.length) { //Get the first node in the queue let node = queue.shift(); //Get the next value in the array let val = arr.shift(); //Check if the value is "null" if(val === "null") { //Do nothing } else { //Create a new node with the value let left = new TreeNode(val); //Set the node's left child to the new node node.left = left; //Push the new node into the queue queue.push(left); } //Get the next value in the array val = arr.shift(); //Check if the value is "null" if(val === "null") { //Do nothing } else { //Create a new node with the value let right = new TreeNode(val); //Set the node's right child to the new node node.right = right; //Push the new node into the queue queue.push(right); } } //Return the root node return root; }
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Codec { public: // Encodes a tree to a single string. string serialize(TreeNode* root) { } // Decodes your encoded data to tree. TreeNode* deserialize(string data) { } }; // Your Codec object will be instantiated and called as such: // Codec codec; // codec.deserialize(codec.serialize(root));
using System; using System.Collections.Generic; public class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int x) { val = x; } } public class Codec { // Encodes a tree to a single string. public string serialize(TreeNode root) { // TODO: Implement this function return null; } // Decodes your encoded data to tree. public TreeNode deserialize(string data) { // TODO: Implement this function return null; } } // Your Codec object will be instantiated and called as such: // Codec codec = new Codec(); // codec.deserialize(codec.serialize(root));