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
Hiring now
Get the Oracle interview, not just the prep
landed applies to roles like these for you, on each company’s own site, with answers written for the role.
Next question