# LeetCode - Count Good Nodes in Binary Tree

## Problem statement

Given a binary tree `root`, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.

Return the number of good nodes in the binary tree.

Problem statement taken from: https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix

Example 1:

``````Input: root = [3, 1, 4, 3, null, 1, 5]
Output: 4
Explanation: Nodes in blue are good.
Root Node (3) is always a good node.
Node 4 -> (3, 4) is the maximum value in the path starting from the root.
Node 5 -> (3, 4, 5) is the maximum value in the path
Node 3 -> (3, 1, 3) is the maximum value in the path.
``````

Example 2:

``````Input: root = [3, 3, null, 4, 2]
Output: 3
Explanation: Node 2 -> (3, 3, 2) is not good, because '3' is higher than it.
``````

Example 3:

``````Input: root = [1]
Output: 1
Explanation: Root is considered as good.
``````

Constraints:

``````- The number of nodes in the binary tree is in the range [1, 10^5].
- Each node's value is between [-10^4, 10^4].
``````

### Explanation

#### DFS recursion

It's one of the easiest problem on LeetCode. We recursively iterate over the tree and keep track of the maximum value in each iteration. We consider the node if it's greater than the parent node.

Let's check the algorithm for this approach.

#### Algorithm

``````// goodNodes function
- return dfs(root)

// dfs function
- if root == NULL
- return 0

- return (root->val >= maximumTillNow ? (maximumTillNow = root->val, 1) : 0) +
dfs(root->left, maximumTillNow) +
dfs(root->right, maximumTillNow)
``````

The time complexity of this approach is O(n) and space complexity is O(n * log(n)).

#### C++ solution

``````class Solution {
public:
int dfs(TreeNode* root, int maximumTillNow = INT_MIN) {
if(root == NULL) {
return 0;
}

return (root->val >= maximumTillNow ? (maximumTillNow = root->val, 1) : 0) +
dfs(root->left, maximumTillNow) +
dfs(root->right, maximumTillNow);
}

int goodNodes(TreeNode* root) {
return dfs(root);
}
};``````

#### Golang solution

``````func dfs(root *TreeNode, maximumTillNow int) int {
if root == nil {
return 0
}

if root.Val >= maximumTillNow {
maximumTillNow = root.Val
}

return addCount + dfs(root.Left, maximumTillNow) + dfs(root.Right, maximumTillNow)
}

func goodNodes(root *TreeNode) int {
return dfs(root, math.MinInt)
}``````

#### JavaScript solution

``````var dfs = function(root, maximumTillNow) {
if(root === null) {
return 0;
}

if(root.val >= maximumTillNow) {
maximumTillNow = root.val;
}

return addCount + dfs(root.left, maximumTillNow) + dfs(root.right, maximumTillNow);
}

var goodNodes = function(root) {
return dfs(root, root.val)
};``````

#### Dry Run

Let's dry-run our algorithm to see how the solution works.

``````Input: root = [3, 1, 4, 3, null, 1, 5]

// goodNodes function
Step 1: return dfs(root)
root -> 3

// dfs function
Step 2: if root == NULL
root -> 3
false

root->val >= maximumTillNow
3 >= INT_MIN
true

maximumTillNow = root->val
= 3

return (root->val >= maximumTillNow ? (maximumTillNow = root->val, 1) : 0) +
dfs(root->left, maximumTillNow) +
dfs(root->right, maximumTillNow)

return 1 + dfs(1, 3) + dfs(4, 3)

// dfs(1, 3)
Step 3: if root == NULL
root -> 1
false

root->val >= maximumTillNow
1 >= 3
false

return (root->val >= maximumTillNow ? (maximumTillNow = root->val, 1) : 0) +
dfs(root->left, maximumTillNow) +
dfs(root->right, maximumTillNow)

return 0 + dfs(3, 3) + dfs(null, 3)

// dfs(3, 3)
Step 4: if root == NULL
root -> 3
false

root->val >= maximumTillNow
3 >= 3
true

maximumTillNow = root->val
= 3

return (root->val >= maximumTillNow ? (maximumTillNow = root->val, 1) : 0) +
dfs(root->left, maximumTillNow) +
dfs(root->right, maximumTillNow)

return 1 + dfs(null, 3) + dfs(null, 3)

dfs(null, 3) returns 0

We return 1 + 0 + 0 = 1

We backtrack to Step 3

// dfs(1, 3)
Step 5: return 0 + dfs(3, 3) + dfs(null, 3)
0 + 1 + 0

return 1

We backtrack to Step 2

// dfs(3, INT_MIN)
Step 6: return 1 + dfs(1, 3) + dfs(4, 3)
1 + 1 + dfs(4, 3)

// dfs(4, 3)
Step 7: if root == NULL
root -> 4
false

root->val >= maximumTillNow
4 >= 3
true

maximumTillNow = root->val
= 4

return (root->val >= maximumTillNow ? (maximumTillNow = root->val, 1) : 0) +
dfs(root->left, maximumTillNow) +
dfs(root->right, maximumTillNow)

return 1 + dfs(1, 4) + dfs(5, 4)

// dfs(1, 4)
Step 8: if root == NULL
root -> 1
false

root->val >= maximumTillNow
1 >= 4
false

return (root->val >= maximumTillNow ? (maximumTillNow = root->val, 1) : 0) +
dfs(root->left, maximumTillNow) +
dfs(root->right, maximumTillNow)

return 0 + dfs(null, 4) + dfs(null, 4)

dfs(null, 4) returns 0

We return 0 + 0 + 0 = 0

We backtrack to Step 7

// dfs(4, 3)
Step 9: return 1 + dfs(1, 4) + dfs(5, 4)
1 + 0 + dfs(5, 4)

// dfs(5, 4)
Step 10: if root == NULL
root -> 5
false

root->val >= maximumTillNow
5 >= 4
true

maximumTillNow = root->val
= 5

return (root->val >= maximumTillNow ? (maximumTillNow = root->val, 1) : 0) +
dfs(root->left, maximumTillNow) +
dfs(root->right, maximumTillNow)

return 1 + dfs(null, 5) + dfs(null, 5)

dfs(null, 5) returns 0

We return 1 + 0 + 0 = 1

We backtrack to Step 9

// dfs(4, 3)
Step 11: return 1 + 0 + dfs(5, 4)
1 + 0 + 1
2

We backtrack to Step 9

// dfs(4, 3)
Step 12: return 1 + 0 + dfs(5, 4)
1 + 0 + 1
2

We backtrack to Step 6

// dfs(3, INT_MIN)
Step 13: return 1 + 1 + dfs(4, 3)
1 + 1 + 2
4

// goodNodes
Step 14: return dfs(root)
4

We return the answer as 4.
``````