Serialize and De-serialize BT
OracleThe problem
Serialization is converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. Ensure that a binary tree can be serialized to a string, and this string can be deserialized to the original tree structure.
The encoded string should be as compact as possible.
Input : root = [2, 1, 3] Output : [2, 1, 3]
Input : root = [7, 3, 15, null, null, 9, 20] Output : [7, 3, 15, null, null, 9, 20]
Input : root = [10, 20, 30, 40, 50, 60]
- 1 <= Number of Nodes <= 104
- 0 <= Node.val <= 104
cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int data;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int val) : data(val) , left(nullptr) , right(nullptr) {}
* };
**/
class Solution {
public:
string serialize(TreeNode* root) {
}
TreeNode* deserialize(string data) {
}
};
/*
* Your Codec object will be instantiated and called as such:
* Codec* ser = new Codec();
* Codec* deser = new Codec();
* string tree = ser->serialize(root);
* TreeNode* ans = deser->deserialize(tree);
* return ans;
*/java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int data;
* TreeNode left;
* TreeNode right;
* TreeNode(int val) { data = val; left = null, right = null }
* }
**/
class Solution {
public String serialize(TreeNode root) {
}
public TreeNode deserialize(String data) {
}
}
/*
* Your Codec object will be instantiated and called as such:
* Codec ser = new Codec();
* Codec deser = new Codec();
* String tree = ser.serialize(root);
* TreeNode ans = deser.deserialize(tree);
* return ans;
*/python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.data = val
# self.left = left
# self.right = right
class Solution:
def serialize(self, root):
"""
:type root: TreeNode
:rtype: string
"""
def deserialize(self, data):
"""
:type root: string
:rtype: TreeNode
"""
# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# tree = ser.serialize(root)
# ans = deser.deserialize(tree)
# return ansjavascript
/**
* Definition for a binary tree node.
* class TreeNode {
* constructor(val = 0, left = null, right = null){
* this.data = val;
* this.left = null;
* this.right = null;
* }
* }
**/
class Solution {
serialize(root) {
}
deserialize(data) {
}
}
/*
* Your Codec object will be instantiated and called as such:
* var ser = new Codec();
* var deser = new Codec();
* var tree = ser.serialize(root);
* var ans = deser.deserialize(tree);
* return ans;
*/csharp
$1fgo
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Data int
* Left *TreeNode
* Right *TreeNode
* }
* func NewTreeNode(val int) *TreeNode {
* return &TreeNode{Data: val}
* }
*/
func serialize(root *TreeNode) string {
}
func deserialize(data string) *TreeNode {
}Stuck? Show a way to structure it+
- 01Choose a traversal and explicit null marker.
- 02Serialize every structural position, not only values.
- 03Deserialize in the same order using a queue of parents.
- 04Define the empty-tree representation.
Reference answer
Then expect these follow-ups
How would you make the encoding more compact?
Tests: format design
How would you validate malformed serialized input?
Tests: robust parsing
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question