Leetcode 1448: Count Good Nodes in Binary Tree
Given the root of a binary tree, a node is considered ‘good’ if in the path from the root to that node, there are no nodes with a value greater than the node itself. Return the total number of good nodes in the tree.
Problem
Approach
Steps
Complexity
Input: The binary tree is represented by its root node. Each node contains a value and pointers to its left and right child nodes.
Example: Input: root = [4, 2, 7, 1, 3, 6, 9]
Constraints:
• The number of nodes in the tree is in the range [1, 10^5].
• Each node's value lies in the range [-10^4, 10^4].
Output: An integer representing the total count of good nodes in the tree.
Example: Output: 5
Constraints:
• The count must include the root node since it is always considered 'good'.
Goal: Count the number of nodes in the tree that are 'good' as per the defined criteria.
Steps:
• Traverse the tree using Depth-First Search (DFS).
• At each node, check if its value is greater than or equal to the maximum value encountered so far along the path from the root.
• If the node satisfies the condition, increment the count of good nodes.
• Update the maximum value encountered so far and recursively traverse the left and right subtrees.
Goal: Conditions to ensure correctness and efficiency of the solution.
Steps:
• The tree may have up to 10^5 nodes, so the algorithm should handle large inputs efficiently.
• Node values can be negative, zero, or positive.
Assumptions:
• The tree is non-empty and has at least one node (the root).
• Node values are integers.
• Input: Input: root = [5, 3, 8, 2, 4, 7, 9]
• Explanation: Output: 5. Nodes 5, 8, 9, 3, and 4 are good. The path from the root to each of these nodes does not contain a value greater than the node.
• Input: Input: root = [10, 9, 11]
• Explanation: Output: 3. All nodes are good as there are no values greater than themselves in their respective paths.
• Input: Input: root = [6, 2, 8, 1, 4]
• Explanation: Output: 4. Nodes 6, 8, 4, and 1 are good. Node 2 is not good as 6 is greater than 2 in the path.
Approach: Use a recursive Depth-First Search (DFS) algorithm to traverse the binary tree and count the good nodes.
Observations:
• The root node is always good.
• The condition for a node being good depends on the maximum value seen along the path from the root.
• A recursive traversal is suitable to track the path's maximum value dynamically.
• Using DFS ensures that we visit each node and evaluate its goodness efficiently.
Steps:
• Define a helper function `good(TreeNode* node, int maxVal)` to perform DFS.
• If the current node is null, return 0.
• Check if the current node's value is greater than or equal to `maxVal`. If true, increment the count.
• Update `maxVal` to be the maximum of its current value and the node's value.
• Recursively call the helper function for the left and right child nodes with the updated `maxVal`.
• Sum the results from the left and right subtrees along with the current node's count.
Empty Inputs:
• Input: root = null -> Output: 0. An empty tree has no good nodes.
Large Inputs:
• Input: A tree with 10^5 nodes -> Should handle efficiently within O(n) time complexity.
Special Values:
• Input: root = [1] -> Output: 1. The single node is good by default.
• Input: root = [3, 3, null, 4, 2] -> Special case where some nodes are not good due to a greater ancestor node.
Constraints:
• Tree depth is large; ensure no stack overflow occurs with recursion.
int goodNodes(TreeNode* root) {
return good(root, -100000);
}
int good(TreeNode* node, int mx) {
if(node == NULL) return 0;
int res = (node->val >= mx) ? 1: 0;
res += good(node->left, max(mx, node->val));
res += good(node->right, max(mx, node->val));
return res;
}
1 : Function Declaration
int goodNodes(TreeNode* root) {
This is the function header where the return type is an integer, and the parameter is a pointer to a TreeNode (the root of the tree).
2 : Function Call
return good(root, -100000);
This line calls the helper function 'good' with the root node and an initial value for 'mx' as a very low value (-100000) to start the comparison.
3 : Helper Function Declaration
int good(TreeNode* node, int mx) {
This is the helper function 'good' that recursively counts the good nodes in the tree. It takes a TreeNode pointer (node) and an integer (mx) which keeps track of the maximum value encountered along the path from the root.
4 : Conditional Check
if(node == NULL) return 0;
This is the base case for the recursion. If the current node is NULL (i.e., we've reached a leaf's child), return 0, meaning no good node here.
5 : Conditional Assignment
int res = (node->val >= mx) ? 1: 0;
Check if the current node's value is greater than or equal to the maximum value ('mx') encountered so far. If true, it is a good node, so set 'res' to 1, otherwise set it to 0.
6 : Recursive Call
res += good(node->left, max(mx, node->val));
Recursively call the 'good' function for the left child, passing the maximum of the current node's value and 'mx' to ensure the path's maximum value is updated.
7 : Recursive Call
res += good(node->right, max(mx, node->val));
Recursively call the 'good' function for the right child, again updating the maximum value encountered along the path.
8 : Return Statement
return res;
Return the total count of good nodes found in the current subtree.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: Each node is visited once, leading to linear time complexity relative to the number of nodes in the tree.
Best Case: O(1)
Worst Case: O(h)
Description: The space complexity is determined by the recursion stack, which depends on the height of the tree (`h`). In the worst case (skewed tree), it could be O(n).
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus