- Problem Statement<\/a><\/li>
- Sample Test Cases<\/a><\/li>
- Depth First Search Traversal-based Approach<\/a><\/li>
- C++ Code<\/a><\/li>
- Java Code<\/a><\/li>
- Python Code<\/a><\/li><\/ul>
- FAQs<\/a><\/li>
- Q.1: What traversal algorithm is used in the approach for the above problem?<\/a><\/li>
- Q.2: What is the significance of the marker variable in the above problem?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n
Problem Statement<\/h2>\n\n\n\n
Given a binary tree, serialize and deserialize the binary tree.<\/p>\n\n\n\n
- Serialize: <\/strong>Write the tree into a file.<\/li>
- Deserialize:<\/strong> Read the tree from a file and reconstruct the binary tree into memory.<\/li><\/ul>\n\n\n\n
Sample Test Cases<\/h2>\n\n\n\n
Input 1:<\/strong><\/p>\n\n\n\n
<\/figure><\/div>\n\n\n\n
Output 1:<\/strong>
[1,2,3,null,null,4,5]\n\n\n\nInput 2:<\/strong> []\n\n\n\n
Output 2:
[] \/\/ Empty tree<\/p>\n\n\n\nDepth First Search Traversal-based Approach<\/h2>\n\n\n\n
We can solve this problem with a Depth First Search Traversal-based algorithm. The idea is to perform a DFS on the tree and serialize individual nodes to the output stream recursively. The traversal used here will be a pre-order traversal. To help in the process of deserializing the tree, we will use some marker variables to represent a null pointer.<\/p>\n\n\n\n
Consider the above image, in this binary tree, the marker Mi represents the null nodes which make the process of deserializing the binary tree easier. The numbering of the markers merely represents the relative positioning of the marker with respect to each other.<\/p>\n\n\n\n
The serialized tree, of the above binary tree, would look like this image.
During deserializing the tree, we will make a new node for every node which is not a marker node, while doing a pre-order traversal on the tree.<\/p>\n\n\n\nC++ Code<\/h3>\n\n\n\n
const int MARKER = INT_MIN\nvoid serialize(TreeNode * node, ostream & sstream) {\n if (node == nullptr) {\n sstream.write((char * ) & MARKER, sizeof(MARKER));\n return;\n }\n sstream.write((char * ) & node -> data, sizeof(node -> data));\n serialize(node -> left, sstream);\n serialize(node -> right, sstream);\n}\n\nTreeNode * deserialize(istream & sstream) {\n if (sstream.eof() == true) {\n return nullptr;\n }\n int value;\n sstream.read((char * ) & value, sizeof(value));\n if (value == MARKER) {\n return nullptr;\n }\n\n TreeNode * newNode = new TreeNode(value);\n newNode -> left = deserialize(sstream);\n newNode -> right = deserialize(sstream);\n\n return newNode;\n}<\/pre>\n\n\n\nJava Code<\/h3>\n\n\n\n
static final int MARKER = Integer.MIN_VALUE;\n\n public static void serialize(TreeNode node, ObjectOutputStream stream) throws java.io.IOException {\n if (node == null) {\n stream.writeInt(MARKER);\n return;\n }\n\n stream.writeInt(node.data);\n serialize(node.left, stream);\n serialize(node.right, stream);\n }\n\n public static TreeNode deserialize(ObjectInputStream stream) throws java.io.IOException {\n int value = stream.readInt();\n if (value == MARKER) {\n return null;\n }\n\n TreeNode node = new TreeNode(val);\n node.left = deserialize(stream);\n node.right = deserialize(stream);\n return node;\n }<\/pre>\n\n\n\nPython Code<\/h3>\n\n\n\n
MARKER = 99999999999\ndef serialize(node, stream):\n if node == None:\n stream.dump(MARKER);\n return\n stream.dump(node.data);\n serialize(node.left, stream)\n serialize(node.right, stream)\n\ndef deserialize(stream):\n try:\n value = pickle.load(stream)\n if value == MARKER:\n return None\n else:\n node = BinaryTreeNode(data);\n node.left = deserialize(stream)\n node.right = deserialize(stream)\n return node\n except pickle.UnpicklingError:\n return None<\/pre>\n\n\n\n
Complexity Analysis<\/strong><\/p>\n\n\n\n
Time Complexity:<\/strong> O(n)
Space Complexity:<\/strong> O(logn)<\/p>\n\n\n\nFAQs<\/h2>\n\n\n\n
Q.1: What traversal algorithm is used in the approach for the above problem?<\/span><\/h3>\n\n\n\n
Ans<\/strong>. A Depth-First Search(DFS) is used to solve the above problem.<\/p>\n\n\n\n
Q.2: What is the significance of the marker variable in the above problem?<\/span><\/h3>\n\n\n\n
Ans.<\/strong> The marker variable is used to signify the null nodes of the tree, which helps in de-serializing the binary tree.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given a binary tree, serialize and deserialize the binary tree. Serialize: Write the tree into a…\n","protected":false},"author":5,"featured_media":5112,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[395,689],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/5057"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=5057"}],"version-history":[{"count":6,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/5057\/revisions"}],"predecessor-version":[{"id":20694,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/5057\/revisions\/20694"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/5112"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=5057"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=5057"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=5057"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
- Deserialize:<\/strong> Read the tree from a file and reconstruct the binary tree into memory.<\/li><\/ul>\n\n\n\n
- Q.2: What is the significance of the marker variable in the above problem?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n
- Java Code<\/a><\/li>
- Sample Test Cases<\/a><\/li>
![\"\"](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/image2-4-1024x937.png\")
<\/figure><\/div>\n\n\n\n![\"\"](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/image1-6-1024x692.png\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/12\/image3-2-1024x95.png\")
<\/figure>\n\n\n\n