codekofi
← All questions

Kth Smallest Element in a BST

HardTrees

The problem

Given a binary search tree and a number k, return the kth smallest value it holds, counting from one.

Return -1 if the tree holds fewer than k values.

kthSmallest({3, 1, 4, nullopt, 2}, 1)

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
44int kthSmallest(const vector<optional<int>>& level, int k) {
45
46 stack<Node*> pending;
47 Node* node = build(level);
48
49 while (node || !pending.empty()) {
50
51 while (node) {
52 pending.push(node);
53 node = node->left;
54 }
55
56 node = pending.top();
57 pending.pop();
58
59 k--;
60
61 if (k == 0) {
62 return node->val;
63 }
64
65 node = node->right;
66 }
67
68 return -1;
69}
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
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
43int kthSmallest(const vector<optional<int>>& level, int k) {
44
45 stack<Node*> pending;
46 Node* node = build(level);
47
48 while (node || !pending.empty()) {
49
50 while (node) {
51 pending.push(node);
52 node = node->left;
53 }
54
55 node = pending.top();
56 pending.pop();
57
58 k--;
59
60 if (k == 0) {
61 return node->val;
62 }
63
64 node = node->right;
65 }
66
67 return -1;
68}
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
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
43int kthSmallest(const vector<optional<int>>& level, int k) {
44
45 stack<Node*> pending;
46 Node* node = build(level);
47
48 while (node || !pending.empty()) {
49
50 while (node) {
51 pending.push(node);
52 node = node->left;
53 }
54
55 node = pending.top();
56 pending.pop();
57
58 k--;
59
60 if (k == 0) {
61 return node->val;
62 }
63
64 node = node->right;
65 }
66
67 return -1;
68}