Solution For Count Good Nodes In Binary Tree
Problem statement:
Given a binary tree, a node is called “good” if it satisfies the following conditions:
- It is a leaf node.
- Its value is greater than or equal to the maximum value of any node in its left subtree.
- Its value is less than or equal to the minimum value of any node in its right subtree.
Return the number of good nodes in the binary tree.
Example:
Input: root = [3,1,4,3,null,1,5]
Output: 4
Explanation: There are 4 good nodes in the binary tree: 3, 4, 5, and 3 (again).
Solution:
This problem can be solved by traversing the binary tree in a depth-first manner. We can maintain a variable count that stores the number of good nodes we have found so far. Whenever we visit a node during the traversal, we check if it is a good node or not according to the conditions mentioned above.
To check if a node is a good node, we need to keep track of the maximum and minimum values seen so far in its left and right subtrees separately. We can pass these values as parameters to the recursive function that traverses the tree.
We can start by initializing these maximum and minimum values as null for the root node. For each node, we can update the maximum value in its left subtree to the maximum of its current maximum and the value of the current node. Similarly, we can update the minimum value in its right subtree to the minimum of its current minimum and the value of the current node. Then we can check if the current node satisfies the conditions for being a good node by comparing its value with the maximum and minimum values seen so far in its left and right subtrees.
Here is the implementation of this algorithm in Python:
class Solution:
def goodNodes(self, root: TreeNode) -> int:
return self.countGoodNodes(root, root.val)
def countGoodNodes(self, node, max_so_far):
if node is None:
return 0
count = 0
if node.val >= max_so_far:
count += 1
max_so_far = node.val
count += self.countGoodNodes(node.left, max_so_far)
count += self.countGoodNodes(node.right, max_so_far)
return count
In this implementation, we have defined a recursive function countGoodNodes that takes two parameters: the current node and the maximum value seen so far in the current path. We initialize this maximum value as the value of the root node when we call the function for the first time.
Inside the function, we first check if the current node satisfies the conditions for being a good node. If it does, we add one to the count of good nodes and update the maximum value seen so far to the value of the current node.
Then we recursively call the function for the left and right subtrees of the current node, passing the updated maximum value seen so far. Finally, we return the total count of good nodes found in the tree.
Time complexity: O(N), where N is the number of nodes in the tree. We need to visit each node once during the traversal.
Space complexity: O(H), where H is the height of the tree. The space required by the call stack of the recursive function is proportional to the height of the tree. In the worst case (skewed tree), the height of the tree can be N, so the space complexity would be O(N) in that case.
Step by Step Implementation For Count Good Nodes In Binary Tree
/**
* 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 maxValue) {
if (node == null) {
return 0;
}
int isGoodNode = node.val >= maxValue ? 1 : 0;
maxValue = Math.max(maxValue, node.val);
return isGoodNode + dfs(node.left, maxValue) + dfs(node.right, maxValue);
}
}# 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:
# keep track of the maximum value seen so far
max_val = -float('inf')
# use a stack to perform a depth-first search
stack = [root]
# keep track of the number of good nodes
num_good = 0
# perform a depth-first search
while stack:
# pop the next node from the stack
node = stack.pop()
# if the current node is a good node, increment the count
if node.val >= max_val:
num_good += 1
# update the maximum value seen so far
max_val = node.val
# if the node has a left child, add it to the stack
if node.left:
stack.append(node.left)
# if the node has a right child, add it to the stack
if node.right:
stack.append(node.right)
# return the number of good nodes
return num_good/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var goodNodes = function(root) {
// keep track of the maximum value seen so far
let maxValue = -Infinity;
// recursive helper function
const dfs = (node) => {
// base case - if node is null, return
if (!node) return;
// if node's value is greater than the maximum value seen so far,
// increment the count of good nodes
if (node.val >= maxValue) {
maxValue = node.val;
count++;
}
// recurse on left and right child nodes
dfs(node.left);
dfs(node.right);
}
// call helper function on root node
dfs(root);
// return count of good nodes
return count;
};/**
* 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 count = 0;
dfs(root, root->val, count);
return count;
}
void dfs(TreeNode* node, int maxVal, int& count) {
if (!node) return;
if (node->val >= maxVal) {
maxVal = node->val;
count++;
}
dfs(node->left, maxVal, count);
dfs(node->right, maxVal, count);
}
};/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution {
public int GoodNodes(TreeNode root) {
// return GoodNodesHelper(root, root.val);
return GoodNodesIterative(root);
}
// Time complexity: O(n)
// Space complexity: O(h), where h is the height of the tree
private int GoodNodesHelper(TreeNode node, int maxValue) {
if (node == null) {
return 0;
}
int count = 0;
if (node.val >= maxValue) {
count++;
}
maxValue = Math.Max(maxValue, node.val);
return count + GoodNodesHelper(node.left, maxValue) + GoodNodesHelper(node.right, maxValue);
}
// Time complexity: O(n)
// Space complexity: O(n)
private int GoodNodesIterative(TreeNode root) {
if (root == null) {
return 0;
}
int count = 0;
var stack = new Stack>();
stack.Push(new Tuple(root, root.val));
while (stack.Count > 0) {
var tuple = stack.Pop();
var node = tuple.Item1;
var maxValue = tuple.Item2;
if (node.val >= maxValue) {
count++;
}
maxValue = Math.Max(maxValue, node.val);
if (node.left != null) {
stack.Push(new Tuple(node.left, maxValue));
}
if (node.right != null) {
stack.Push(new Tuple(node.right, maxValue));
}
}
return count;
}
} 