Count Good Nodes In Binary Tree
Counting Nodes which are Good in a Binary Tree
In a binary tree, a node x is considered a good node if, on the path from the root of the tree to x, no other node has a value greater than x. In other words, a node is good if its value is the largest (or equal to the largest) seen so far along its path from the root.
You are given the root of a binary tree, and the task is to calculate and return the total number of good nodes present in the tree.
Example 1
Output: 3
Output: 4
Constraints:
- 1 <= number of nodes in the tree <= 100
- -100 <= Node.val <= 100
Maximum Depth of Binary Tree
Recommendation for Time and Space Complexity – You should aim for a solution with O(n) time and O(n) space, where n is the number of nodes in the given tree.
Hints for solving problems
Hint 1 :
A brute force solution would involve considering every node and checking if the path from the root to that node is valid, resulting in an O(n^2) time complexity. Can you think of a better approach?
Hint 2 :
We can use the Depth First Search (DFS) algorithm to traverse the tree. But can you think of a way to determine if the current node is a good node in a single traversal? Maybe we need to track a value while traversing the tree.
There are mainly 2 approach to solve this problem-
- Depth First Search Method
- Breadth First Search Method
1. Depth First Search Method
In this method, we traverse the tree recursively, keeping track of the maximum value seen so far along the path. At each node, we check if its value is greater than or equal to the maximum value and update the count accordingly. The maximum value is also updated as we move deeper into the tree.
- Time complexity: O(n)
- Space complexity: O(n)
Code
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int goodNodes(TreeNode* root) {
return dfs(root, root->val);
}
private:
int dfs(TreeNode* node, int maxVal) {
if (!node) {
return 0;
}
int res = (node->val >= maxVal) ? 1 : 0;
maxVal = max(maxVal, node->val);
res += dfs(node->left, maxVal);
res += dfs(node->right, maxVal);
return res;
}
};
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int goodNodes(TreeNode root) {
return dfs(root, root.val);
}
private int dfs(TreeNode node, int maxVal) {
if (node == null) {
return 0;
}
int res = (node.val >= maxVal) ? 1 : 0;
maxVal = Math.max(maxVal, node.val);
res += dfs(node.left, maxVal);
res += dfs(node.right, maxVal);
return res;
}
}
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def goodNodes(self, root: TreeNode) -> int:
def dfs(node, maxVal):
if not node:
return 0
res = 1 if node.val >= maxVal else 0
maxVal = max(maxVal, node.val)
res += dfs(node.left, maxVal)
res += dfs(node.right, maxVal)
return res
return dfs(root, root.val)
/**
* Definition for a binary tree node.
* class TreeNode {
* constructor(val = 0, left = null, right = null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
/**
* @param {TreeNode} root
* @return {number}
*/
goodNodes(root) {
return this.dfs(root, root.val);
}
/**
* @param {TreeNode} node
* @param {number} maxVal
* @return {number}
*/
dfs(node, maxVal) {
if (!node) {
return 0;
}
let res = node.val >= maxVal ? 1 : 0;
maxVal = Math.max(maxVal, node.val);
res += this.dfs(node.left, maxVal);
res += this.dfs(node.right, maxVal);
return res;
}
}
2. Breadth First Search Method
This approach uses a queue to perform a level-by-level traversal of the tree. Along with each node, we store the maximum value seen so far on its path. At each step, we compare the node’s value with the maximum value, update the count if it’s a good node, and propagate the updated maximum value to its children.
- Time complexity: O(n)
- Space complexity: O(n)
Code
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int goodNodes(TreeNode* root) {
int res = 0;
queue> q;
q.push({root, -INT_MAX});
while (!q.empty()) {
auto [node, maxval] = q.front();
q.pop();
if (node->val >= maxval) {
res++;
}
if (node->left) {
q.push({node->left, max(maxval, node->val)});
}
if (node->right) {
q.push({node->right, max(maxval, node->val)});
}
}
return res;
}
};
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution {
public int goodNodes(TreeNode root) {
int res = 0;
Queue> q = new LinkedList<>();
q.offer(new Pair<>(root, Integer.MIN_VALUE));
while (!q.isEmpty()) {
Pair pair = q.poll();
TreeNode node = pair.getKey();
int maxval = pair.getValue();
if (node.val >= maxval) {
res++;
}
if (node.left != null) {
q.offer(new Pair<>(node.left, Math.max(maxval, node.val)));
}
if (node.right != null) {
q.offer(new Pair<>(node.right, Math.max(maxval, node.val)));
}
}
return res;
}
}
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def goodNodes(self, root: TreeNode) -> int:
res = 0
q = deque()
q.append((root,-float('inf')))
while q:
node,maxval = q.popleft()
if node.val >= maxval:
res += 1
if node.left:
q.append((node.left,max(maxval,node.val)))
if node.right:
q.append((node.right,max(maxval,node.val)))
return res
/**
* Definition for a binary tree node.
* class TreeNode {
* constructor(val = 0, left = null, right = null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
/**
* @param {TreeNode} root
* @return {number}
*/
goodNodes(root) {
let res = 0;
let q = new Queue();
q.push([root, -Infinity]);
while (!q.isEmpty()) {
let [node, maxval] = q.pop();
if (node.val >= maxval) {
res++;
}
if (node.left) {
q.push([node.left, Math.max(maxval, node.val)]);
}
if (node.right) {
q.push([node.right, Math.max(maxval, node.val)]);
}
}
return res;
}
}
