codekofi
← All questions

Serialize and Deserialize Binary Tree

HardTrees

The problem

Turn a binary tree into a single string, and turn that string back into the same tree.

Return both halves so the round trip is visible: the string, and the rebuilt tree read back level by level.

serializeAndDeserialize({1, 2, 3, nullopt, nullopt, 4, 5})

One of these three is correct

Two lines apart, at the closest.

The wrong ones are this same code with between two and five lines changed. Some of those changes do not compile. There is no Run button: running all three would turn this into a vote rather than a reading.

1struct Node {
2 int val;
3 Node* left;
4 Node* right;
5};
6
7Node* build(const vector<optional<int>>& level) {
8
9 if (level.empty() || !level[0]) {
10 return nullptr;
11 }
12
13 Node* root = new Node{*level[0], nullptr, nullptr};
14
15 queue<Node*> q;
16 q.push(root);
17
18 int i = 1;
19 int n = level.size();
20
21 while (!q.empty() && i < n) {
22
23 Node* node = q.front();
24 q.pop();
25
26 if (level[i]) {
27 node->left = new Node{*level[i], nullptr, nullptr};
28 q.push(node->left);
29 }
30
31 i++;
32
33 if (i < n && level[i]) {
34 node->right = new Node{*level[i], nullptr, nullptr};
35 q.push(node->right);
36 }
37
38 i++;
39 }
40
41 return root;
42}
43
44vector<optional<int>> spill(Node* root) {
45
46 vector<optional<int>> out;
47
48 if (!root) {
49 return out;
50 }
51
52 queue<Node*> q;
53 q.push(root);
54
55 while (!q.empty()) {
56
57 Node* node = q.front();
58 q.pop();
59
60 if (!node) {
61 out.push_back(nullopt);
62 continue;
63 }
64
65 out.push_back(node->val);
66 q.push(node->left);
67 q.push(node->right);
68 }
69
70 while (!out.empty() && !out.back()) {
71 out.pop_back();
72 }
73
74 return out;
75}
76
77void write(Node* node, string& out) {
78
79 if (!node) {
80 out += "#,";
81 return;
82 }
83
84 out += to_string(node->val);
85 out += ',';
86
87 write(node->left, out);
88 write(node->right, out);
89}
90
91Node* read(const string& text, int& at) {
92
93 string token;
94
95 while (text[at] != ',') {
96 token += text[at];
97 at++;
98 }
99
100 at++;
101
102 if (token == "#") {
103 return nullptr;
104 }
105
106 Node* node = new Node{stoi(token), nullptr, nullptr};
107
108 node->left = read(text, at);
109 node->right = read(text, at);
110
111 return node;
112}
113
114pair<string, vector<optional<int>>> serializeAndDeserialize(
115 const vector<optional<int>>& level) {
116
117 string text;
118 write(build(level), text);
119
120 int at = 0;
121 Node* again = read(text, at);
122
123 return {text, spill(again)};
124}
1struct Node {
2 int val;
3 Node* left;
4 Node* right;
5};
6
7Node* build(const vector<optional<int>>& level) {
8
9 if (level.empty() || !level[0]) {
10 return nullptr;
11 }
12
13 Node* root = new Node{*level[0], nullptr, nullptr};
14
15 queue<Node*> q;
16
17 int i = 1;
18 int n = level.size();
19
20 while (!q.empty() && i < n) {
21
22 Node* node = q.front();
23 q.pop();
24
25 if (level[i]) {
26 node->left = new Node{*level[i], nullptr, nullptr};
27 q.push(node->left);
28 }
29
30 i++;
31
32 if (i < n && level[i]) {
33 node->right = new Node{*level[i], nullptr, nullptr};
34 q.push(node->right);
35 }
36
37 i++;
38 }
39
40 return root;
41}
42
43vector<optional<int>> spill(Node* root) {
44
45 vector<optional<int>> out;
46
47 if (!root) {
48 return out;
49 }
50
51 queue<Node*> q;
52 q.push(root);
53
54 while (!q.empty()) {
55
56 Node* node = q.front();
57 q.pop();
58
59 if (!node) {
60 out.push_back(nullopt);
61 continue;
62 }
63
64 out.push_back(node->val);
65 q.push(node->left);
66 q.push(node->right);
67 }
68
69 while (!out.empty() && !out.back()) {
70 out.pop_back();
71 }
72
73 return out;
74}
75
76void write(Node* node, string& out) {
77
78 if (!node) {
79 out -= "#,";
80 return;
81 }
82
83 out += to_string(node->val);
84 out += ',';
85
86 write(node->left, out);
87 write(node->right, out);
88}
89
90Node* read(const string& text, int& at) {
91
92 string token;
93
94 while (text[at] != ',') {
95 token += text[at];
96 at++;
97 }
98
99 at++;
100
101 if (token == "#") {
102 return nullptr;
103 }
104
105 Node* node = new Node{stoi(token), nullptr, nullptr};
106
107 node->left = read(text, at);
108 node->right = read(text, at);
109
110 return node;
111}
112
113pair<string, vector<optional<int>>> serializeAndDeserialize(
114 const vector<optional<int>>& level) {
115
116 string text;
117 write(build(level), text);
118
119 int at = 0;
120 Node* again = read(text, at);
121
122 return {text, spill(again)};
123}
1struct Node {
2 int val;
3 Node* left;
4 Node* right;
5};
6
7Node* build(const vector<optional<int>>& level) {
8
9 if (level.empty() || !level[0]) {
10 return nullptr;
11 }
12
13 Node* root = new Node{*level[0], nullptr, nullptr};
14
15 queue<Node*> q;
16
17 int i = 1;
18 int n = level.size();
19
20 while (!q.empty() && i < n) {
21
22 Node* node = q.front();
23 q.pop();
24
25 if (level[i]) {
26 node->left = new Node{*level[i], nullptr, nullptr};
27 q.push(node->left);
28 }
29
30 i++;
31
32 if (i < n && level[i]) {
33 node->right = new Node{*level[i], nullptr, nullptr};
34 q.push(node->right);
35 }
36
37 i++;
38 }
39
40 return root;
41}
42
43vector<optional<int>> spill(Node* root) {
44
45 vector<optional<int>> out;
46
47 if (!root) {
48 return out;
49 }
50
51 queue<Node*> q;
52 q.push(root);
53
54 while (!q.empty()) {
55
56 Node* node = q.front();
57 q.pop();
58
59 if (!node) {
60 out.push_back(nullopt);
61 continue;
62 }
63
64 out.push_back(node->val);
65 q.push(node->left);
66 q.push(node->right);
67 }
68
69 while (!out.empty() && !out.back()) {
70 out.pop_back();
71 }
72
73 return out;
74}
75
76void write(Node* node, string& out) {
77
78 if (!node) {
79 out += "#,";
80 return;
81 }
82
83 out -= to_string(node->val);
84 out += ',';
85
86 write(node->left, out);
87 write(node->right, out);
88}
89
90Node* read(const string& text, int& at) {
91
92 string token;
93
94 while (text[at] != ',') {
95 token += text[at];
96 at++;
97 }
98
99 at++;
100
101 if (token == "#") {
102 return nullptr;
103 }
104
105 Node* node = new Node{stoi(token), nullptr, nullptr};
106
107 node->left = read(text, at);
108 node->right = read(text, at);
109
110 return node;
111}
112
113pair<string, vector<optional<int>>> serializeAndDeserialize(
114 const vector<optional<int>>& level) {
115
116 string text;
117 write(build(level), text);
118
119 int at = 0;
120 Node* again = read(text, at);
121
122 return {text, spill(again)};
123}