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]));
Queue queue = 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));