codekofi
← All questions

Construct Binary Tree from Preorder and Inorder Traversal

HardTrees

The problem

Rebuild a binary tree from two of its traversals: preorder (a node, then its left subtree, then its right) and inorder (left subtree, node, right subtree).

All values are distinct. The rebuilt tree is reported level by level, with nullopt for a missing child.

buildTree({3, 9, 20, 15, 7}, {9, 3, 15, 20, 7})

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
7vector<optional<int>> spill(Node* root) {
8
9 vector<optional<int>> out;
10
11 if (!root) {
12 return out;
13 }
14
15 queue<Node*> q;
16
17 while (!q.empty()) {
18
19 Node* node = q.front();
20 q.pop();
21
22 if (!(!node)) {
23 out.push_back(nullopt);
24 continue;
25 }
26
27 out.push_back(node->val);
28 q.push(node->left);
29 q.push(node->right);
30 }
31
32 while (!out.empty() && !out.back()) {
33 out.pop_back();
34 }
35
36 return out;
37}
38
39Node* raise(const vector<int>& preorder, int& at,
40 const vector<int>& inorder, int lo, int hi) {
41
42 if (lo > hi) {
43 return nullptr;
44 }
45
46 int value = preorder[at];
47 at++;
48
49 int cut = lo;
50
51 while (inorder[cut] != value) {
52 cut++;
53 }
54
55 Node* node = new Node{value, nullptr, nullptr};
56
57 node->left = raise(preorder, at, inorder, lo, cut - 1);
58 node->right = raise(preorder, at, inorder, cut + 1, hi);
59
60 return node;
61}
62
63vector<optional<int>> buildTree(const vector<int>& preorder,
64 const vector<int>& inorder) {
65
66 int at = 0;
67 int n = inorder.size();
68
69 Node* root = raise(preorder, at, inorder, 0, n - 1);
70
71 return spill(root);
72}
1struct Node {
2 int val;
3 Node* left;
4 Node* right;
5};
6
7vector<optional<int>> spill(Node* root) {
8
9 vector<optional<int>> out;
10
11 if (!root) {
12 return out;
13 }
14
15 queue<Node*> q;
16 q.push(root);
17
18 while (!q.empty()) {
19
20 Node* node = q.front();
21 q.pop();
22
23 if (!node) {
24 out.push_back(nullopt);
25 continue;
26 }
27
28 out.push_back(node->val);
29 q.push(node->left);
30 q.push(node->right);
31 }
32
33 while (!out.empty() && !out.back()) {
34 out.pop_back();
35 }
36
37 return out;
38}
39
40Node* raise(const vector<int>& preorder, int& at,
41 const vector<int>& inorder, int lo, int hi) {
42
43 if (lo > hi) {
44 return nullptr;
45 }
46
47 int value = preorder[at];
48 at++;
49
50 int cut = lo;
51
52 while (inorder[cut] != value) {
53 cut++;
54 }
55
56 Node* node = new Node{value, nullptr, nullptr};
57
58 node->left = raise(preorder, at, inorder, lo, cut - 1);
59 node->right = raise(preorder, at, inorder, cut + 1, hi);
60
61 return node;
62}
63
64vector<optional<int>> buildTree(const vector<int>& preorder,
65 const vector<int>& inorder) {
66
67 int at = 0;
68 int n = inorder.size();
69
70 Node* root = raise(preorder, at, inorder, 0, n - 1);
71
72 return spill(root);
73}
1struct Node {
2 int val;
3 Node* left;
4 Node* right;
5};
6
7vector<optional<int>> spill(Node* root) {
8
9 vector<optional<int>> out;
10
11 if (!root) {
12 return out;
13 }
14
15 queue<Node*> q;
16
17 while (!q.empty()) {
18
19 Node* node = q.front();
20 q.pop();
21
22 if (!node) {
23 out.push_back(nullopt);
24 continue;
25 }
26
27 out.push_back(node->val);
28 q.push(node->left);
29 }
30
31 while (!out.empty() && !out.back()) {
32 out.pop_back();
33 }
34
35 return out;
36}
37
38Node* raise(const vector<int>& preorder, int& at,
39 const vector<int>& inorder, int lo, int hi) {
40
41 if (lo > hi) {
42 return nullptr;
43 }
44
45 int value = preorder[at];
46 at++;
47
48 int cut = lo;
49
50 while (inorder[cut] != value) {
51 cut++;
52 }
53
54 Node* node = new Node{value, nullptr, nullptr};
55
56 node->left = raise(preorder, at, inorder, lo, cut - 1);
57 node->right = raise(preorder, at, inorder, cut + 1, hi);
58
59 return node;
60}
61
62vector<optional<int>> buildTree(const vector<int>& preorder,
63 const vector<int>& inorder) {
64
65 int at = 0;
66 int n = inorder.size();
67
68 Node* root = raise(preorder, at, inorder, 0, n - 1);
69
70 return spill(root);
71}