Problem Breakdown
We are given a binary tree where each node has an integer value. A node is defined as “good” if its value is greater than or equal to every ancestor in the path from the root down to itself (inclusive). Essentially, we need to count how many nodes satisfy node.val >= max(ancestors).
Inputs:
- The root of a binary tree (
TreeNode). - Node values are integers within
[-10^4, 10^4].
Outputs:
- An integer representing the total count of good nodes.
Implicit Constraints & Edge Cases:
- Path Definition: The path includes the node itself and all ancestors up to the root.
- Root Node: Always considered a “good” node because it has no ancestors with greater values (path length 1).
- Negative Values: Since we are comparing integers, negative numbers behave normally in comparisons;
max()works correctly across signs. - Duplicates: If an ancestor equals the current node’s value (
val == val), the condition holds true (“no nodes with a value greater than X”). Equality is allowed for “good” status. - Tree Depth: With , we must ensure our solution scales linearly () and doesn’t hit recursion limits on skewed trees (though LeetCode environments typically handle standard DFS depth).
Intuition
Brute Force Approach:
For every node, traverse from the root down to that specific node again to find the maximum value encountered. If current_node.val >= max_found, increment count.
- Complexity: in worst case (skewed tree). For each of nodes, we might re-traverse a path up to length . This will Time Out on large inputs ().
Key Insight:
We do not need to look back at ancestors every time. As we traverse down the tree using Depth-First Search (DFS), we can maintain state: specifically, the maximum value seen so far along the current path.
When moving from a parent to a child, this max_so_far is passed as an argument. If the child’s value meets or exceeds this running maximum, it updates the count and passes its own value (or the updated max) down to children.
Optimal Approach:
Use DFS with state passing (current_max). This allows us to visit each node exactly once (). The “state” is simply a single integer representing the highest value encountered on the path from root to current node.
Approach
- Initialize a counter variable (e.g.,
count = 0) or return counts recursively. Returning values is often cleaner in Python than using nonlocal variables for recursion, so we will sum up results:(is_good ? 1 : 0) + left_count + right_count. - Define a recursive helper function
dfs(node, current_max):- Base Case: If
nodeis null, return 0 (no good nodes in empty subtree). - Check Condition: Determine if the current node is “good” by comparing
node.val >= current_max. Add 1 to count if true. In Python, boolean values can be summed directly (True == 1,False == 0), so we return(condition) + dfs(...) + dfs(...) - Update State: Calculate the new maximum for children:
new_max = max(current_max, node.val). Note that we pass this updated max regardless of whether the current node was good or not; it represents the path constraint for descendants. - Recurse: Call helper on left and right children with
node’s value (or new max). Since Python passes integers by value, passing a scalar is safe.
- Base Case: If
- Start DFS from root with an initial maximum of negative infinity (
-float('inf')) to ensure the first node always satisfies the condition relative to “no ancestors”. Alternatively, handle root separately and pass-10^4 - 7(below min constraint). Using-float('inf')is robust. - Return total count from initial call.
Complexity Analysis
- Time Complexity: where is the number of nodes in the tree. We visit each node exactly once performing constant time comparisons and arithmetic operations ().
- Space Complexity: for recursion stack space, where is the height of the binary tree. In a balanced tree, this is . In a skewed (linked-list-like) tree, it degrades to . This fits within standard memory limits ( nodes). Note: For very deep trees in Python environments without
sys.setrecursionlimit, an iterative approach might be safer, but recursive DFS is the standard expected solution for this problem on LeetCode.
Solution
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def countGoodNodes(root):
# Helper function to perform DFS with state passing.
# node: current tree node being visited
# max_so_far: maximum value encountered on the path from root to this node's parent (inclusive)
def dfs(node, max_so_far):
if not node:
return 0
# Check condition and update running maximum
# In Python, boolean True/False can be added directly as integers
# for counting purposes. We pass the updated max to children regardless of current status.
is_good = (node.val >= max_so_far)
new_max = max(max_so_far, node.val)
return is_good + dfs(node.left, new_max) + dfs(node.right, new_max)
if not root:
return 0
# Initialize with negative infinity so any valid integer value at root counts as good.
initial_min = -float('inf')
return dfs(root, initial_min)
Edge Cases Handled
- Single Node Tree: The recursion handles a single node correctly;
dfsreturns 1 (since-inf < root.val). - All Nodes Good: Logic holds as long as values are non-decreasing along paths.
- Negative Values: Python’s comparison operators handle negative integers naturally, so no special logic is required for the range
[-10^4, 10^4]. - Null Root: Although constraints guarantee at least one node, the check
if not rootensures robustness against empty input. - Syntax Correction: Fixed invalid Python ternary syntax (
and ... else) found in original proposal by using boolean arithmetic directly or conditional expression logic compatible with return summation.