Count Good Nodes in Binary Tree
Count Good Nodes in Binary Tree is a medium trees & bst problem solved with the child + ancestor handling pattern.
The best approach, optimal (dfs carrying the path maximum), runs in O(n) time and O(h) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (scan the whole path at every node) up.
Problem
You are given the root of a binary tree. A node X is called good when no node on the path from the root down to X (including the root, excluding X itself) has a value strictly greater than X.val.
Return the number of good nodes in the tree. The root is always good.
Examples
Example 1
- Input
root = [5, 3, 8, 6, null, 7, 9]- Output
4- Why
- Good nodes: 5 (the root), 6 (path 5-3-6), 8 and 9. The 3 is smaller than 5 and the 7 is smaller than 8.
Example 2
- Input
root = [-2, -2, -5]- Output
2- Why
- The left child equals the largest value above it, which still counts. -5 is below -2.
Example 3
- Input
root = [4]- Output
1- Why
- The root has nothing above it, so it is always good.
Constraints
- The number of nodes is in the range
[1, 10^5]. -10^4 <= Node.val <= 10^4
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (scan the whole path at every node) | O(n · h) | O(h) |
| Optimal (DFS carrying the path maximum) | O(n) | O(h) |
1Brute force (scan the whole path at every node)
O(n · h)Each node scans up to h ancestors, where h is the tree height.O(h)The path list and the recursion stack both hold at most h entries.Traverse the tree while keeping the list of values on the current root-to-node path. At each node, scan that list to see if any ancestor is larger.
- DFS with a list
pathof ancestor values. - At a node, it is good if no value in
pathexceeds node.val. - Add node.val to the path, recurse into both children, then remove it.
class Solution {
public int goodNodes(TreeNode root) {
return dfs(root, new ArrayList<>());
}
private int dfs(TreeNode node, List<Integer> path) {
if (node == null) return 0;
boolean good = true;
for (int v : path)
if (v > node.val) { good = false; break; }
path.add(node.val);
int count = (good ? 1 : 0) + dfs(node.left, path) + dfs(node.right, path);
path.remove(path.size() - 1);
return count;
}
}class Solution:
def goodNodes(self, root: Optional[TreeNode]) -> int:
path = []
def dfs(node: Optional[TreeNode]) -> int:
if node is None:
return 0
good = all(v <= node.val for v in path)
path.append(node.val)
count = (1 if good else 0) + dfs(node.left) + dfs(node.right)
path.pop()
return count
return dfs(root)class Solution {
public:
int goodNodes(TreeNode* root) {
vector<int> path;
return dfs(root, path);
}
private:
int dfs(TreeNode* node, vector<int>& path) {
if (!node) return 0;
bool good = true;
for (int v : path)
if (v > node->val) { good = false; break; }
path.push_back(node->val);
int count = (good ? 1 : 0) + dfs(node->left, path) + dfs(node->right, path);
path.pop_back();
return count;
}
};function goodNodes(root) {
const path = [];
const dfs = (node) => {
if (node === null) return 0;
let good = true;
for (const v of path)
if (v > node.val) { good = false; break; }
path.push(node.val);
const count = (good ? 1 : 0) + dfs(node.left) + dfs(node.right);
path.pop();
return count;
};
return dfs(root);
}2Optimal (DFS carrying the path maximum)
O(n)Every node is visited once with constant work.O(h)Recursion depth equals the tree height.The scan in the brute force only ever needs the maximum of the path, and that maximum can be updated in O(1) on the way down. Pass it as an argument: a node is good when its value is at least the maximum, and its children receive max(maximum, node.val).
- dfs(node, maxSoFar): if node is null return 0.
- good = node.val >= maxSoFar ? 1 : 0; newMax = max(maxSoFar, node.val).
- Return good + dfs(left, newMax) + dfs(right, newMax). Start with dfs(root, root.val).
class Solution {
public int goodNodes(TreeNode root) {
return dfs(root, root.val);
}
private int dfs(TreeNode node, int maxSoFar) {
if (node == null) return 0;
int good = node.val >= maxSoFar ? 1 : 0;
int next = Math.max(maxSoFar, node.val);
return good + dfs(node.left, next) + dfs(node.right, next);
}
}class Solution:
def goodNodes(self, root: Optional[TreeNode]) -> int:
def dfs(node: Optional[TreeNode], max_so_far: int) -> int:
if node is None:
return 0
good = 1 if node.val >= max_so_far else 0
nxt = max(max_so_far, node.val)
return good + dfs(node.left, nxt) + dfs(node.right, nxt)
return dfs(root, root.val)class Solution {
public:
int goodNodes(TreeNode* root) {
return dfs(root, root->val);
}
private:
int dfs(TreeNode* node, int maxSoFar) {
if (!node) return 0;
int good = node->val >= maxSoFar ? 1 : 0;
int next = max(maxSoFar, node->val);
return good + dfs(node->left, next) + dfs(node->right, next);
}
};function goodNodes(root) {
const dfs = (node, maxSoFar) => {
if (node === null) return 0;
const good = node.val >= maxSoFar ? 1 : 0;
const next = Math.max(maxSoFar, node.val);
return good + dfs(node.left, next) + dfs(node.right, next);
};
return dfs(root, root.val);
}Edge cases to test
- A single node (answer 1)
- Values equal to the path maximum count as good
- A strictly decreasing chain (only the root is good)
- A strictly increasing chain (every node is good)
- Negative values
Hints
Hint 1
Whether a node is good only depends on the largest value on the path from the root to it.
Hint 2
Pass that largest value down as a parameter while you traverse.
FAQ
What is the best time complexity for Count Good Nodes in Binary Tree?
Optimal (DFS carrying the path maximum) runs in O(n) time and O(h) extra space. Every node is visited once with constant work.
Which pattern does Count Good Nodes in Binary Tree use?
It is a trees & bst problem that uses the child + ancestor handling pattern. Other problems with the same pattern: Amount of Time for Binary Tree to Be Infected, Burning Tree, All Nodes Distance K in Binary Tree.
Is there a brute force solution for Count Good Nodes in Binary Tree?
Yes. Brute force (scan the whole path at every node) takes O(n · h) time and O(h) space. Traverse the tree while keeping the list of values on the current root-to-node path.
Which edge cases should I test for Count Good Nodes in Binary Tree?
A single node (answer 1); Values equal to the path maximum count as good; A strictly decreasing chain (only the root is good); A strictly increasing chain (every node is good); Negative values.