codekofi
← All questions

Count Good Nodes in Binary Tree

HardTrees

The problem

A node is good when no node on the path from the root down to it holds a larger value — that is, it is at least as large as everything above it.

Count the good nodes in the tree. The root is always good.

goodNodes({3, 1, 4, 3, nullopt, 1, 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
17 int i = 0;
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
43int tally(Node* node, int best) {
44
45 if (!node) {
46 return 0;
47 }
48
49 int here = 0;
50
51 if (node->val >= best) {
52 here = 1;
53 }
54
55 best = max(best, node->val);
56
57 int left = tally(node->left, best);
58 int right = tally(node->right, best);
59
60 return here + left + right;
61}
62
63int goodNodes(const vector<optional<int>>& level) {
64
65 Node* root = build(level);
66
67 return tally(root, INT_MIN);
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 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 tally(Node* node, int best) {
45
46 if (!node) {
47 return 0;
48 }
49
50 int here = 0;
51
52 if (node->val >= best) {
53 here = 1;
54 }
55
56 best = max(best, node->val);
57
58 int left = tally(node->left, best);
59 int right = tally(node->right, best);
60
61 return here + left + right;
62}
63
64int goodNodes(const vector<optional<int>>& level) {
65
66 Node* root = build(level);
67
68 return tally(root, INT_MIN);
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 = 0;
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 tally(Node* node, int best) {
45
46 if (!node) {
47 return 0;
48 }
49
50 int here = 0;
51
52 if (node->val >= best) {
53 here = 1;
54 }
55
56 best = max(best, node->val);
57
58 int left = tally(node->left, best);
59 int right = tally(node->right, best);
60
61 return here + left + right;
62}
63
64int goodNodes(const vector<optional<int>>& level) {
65
66 Node* root = build(level);
67
68 return tally(root, INT_MIN);
69}