Problem Description

You are given a binary tree with a root node. A node X in the tree is considered good if along the path from the root to node X, there are no nodes with values greater than X's value.

In other words, a node is good if its value is greater than or equal to all the values of its ancestor nodes (including the root) on the path from root to that node.

Your task is to count and return the total number of good nodes in the binary tree.

For example:

• The root node is always good (no ancestors to compare with)
• A node with value 5 is good if all nodes on the path from root to this node have values ≤ 5
• A node with value 3 would not be good if any ancestor node on its path has a value > 3

The solution uses a depth-first search (DFS) approach where it tracks the maximum value seen so far along each path. Starting from the root with an initial maximum of -1000000 (a very small number), it traverses the tree. At each node, if the current node's value is greater than or equal to the maximum value seen so far on that path (mx <= root.val), the node is counted as good and the maximum is updated. The function recursively checks both left and right subtrees, passing along the updated maximum value for each path.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A binary tree is a special type of graph where each node has at most two children and there are no cycles.

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure with a root node and parent-child relationships.

DFS

• We arrive at DFS: Since we're dealing with a tree structure, the flowchart leads us directly to using Depth-First Search (DFS).

Why DFS is appropriate for this problem:

• We need to traverse from the root to each node while maintaining information about the path (specifically, the maximum value seen so far)
• DFS naturally maintains the path context as we recursively traverse down the tree
• At each node, we need to make a decision based on all ancestors in the current path, which DFS handles perfectly by passing parameters through the recursive calls
• The problem requires visiting every node exactly once to count all good nodes

Conclusion: The flowchart correctly suggests using DFS for this tree traversal problem. The DFS approach allows us to maintain the maximum value encountered along each root-to-node path and efficiently determine whether each node is "good" by comparing it with this tracked maximum.

Intuition

The key insight is that we need to track the maximum value seen along each path from root to the current node. Think of it like walking down a path and keeping track of the highest point you've reached so far.

When we visit a node, we only need to know one piece of information from the path above it: what's the largest value we've encountered so far? If the current node's value is greater than or equal to this maximum, then by definition, no ancestor has a value greater than the current node - making it a "good" node.

This naturally suggests a recursive approach where we:

1. Pass down the maximum value seen so far as we traverse
2. At each node, check if current_value >= max_seen_so_far
3. If yes, increment our count and update the maximum for the subtrees
4. Continue this process for all nodes

Why does this work? Because when we're at any node X, we've already visited all its ancestors (that's how we got to X in the first place). The mx parameter captures the essential information from all those ancestors - their maximum value. We don't need to remember the entire path or all the ancestor values, just the maximum one.

Starting with a very small initial maximum (like -1000000) ensures that the root node is always counted as good, which makes sense since the root has no ancestors to be compared against.

The beauty of this approach is its simplicity - we're reducing the entire path history to a single number (the maximum), making the solution both elegant and efficient with O(n) time complexity and O(h) space complexity where h is the height of the tree.

Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.

Solution Approach

The implementation uses a recursive DFS helper function to traverse the binary tree while maintaining the maximum value seen along each path.

Core Implementation Structure:

1. Helper Function Definition: We define an inner function dfs(root, mx) where:

   • root is the current node being visited
   • mx is the maximum value seen from the root to the current node's parent

2. Base Case: If the current node is None, we simply return (nothing to process).

3. Good Node Check: For each node, we check if mx <= root.val:

   • If true, the current node is good (no ancestor has a greater value)
   • We increment the answer counter using nonlocal ans to modify the outer scope variable
   • We update mx = root.val for the recursive calls to children

4. Recursive Traversal: We recursively call DFS on both children:

   • dfs(root.left, mx) - traverse left subtree with updated maximum
   • dfs(root.right, mx) - traverse right subtree with updated maximum

Key Implementation Details:

• Initial Maximum Value: We start with mx = -1000000, a value smaller than any possible node value in the tree. This ensures the root is always counted as good.

• Nonlocal Variable: The ans variable is declared in the outer function scope and modified using nonlocal keyword. This allows the nested function to accumulate the count across all recursive calls.

• Path Context Preservation: Each recursive call maintains its own mx value. When we go left or right from a node, both branches get the same maximum value up to that point, but their subsequent updates don't affect each other.

Algorithm Flow:

1. Initialize ans = 0 to store the count of good nodes
2. Call dfs(root, -1000000) to start traversal from root
3. At each node:
   • Check if it's good (mx <= root.val)
   • Update count and maximum if needed
   • Recursively process children
4. Return the final count

The time complexity is O(n) where n is the number of nodes (we visit each node exactly once), and the space complexity is O(h) where h is the height of the tree (for the recursion call stack).

Example Walkthrough

Let's walk through a concrete example to understand how the algorithm works.

Consider this binary tree:

        3
       / \
      1   4
     /   / \
    3   1   5

We want to count the good nodes. Remember, a node is "good" if no ancestor has a value greater than it.

Step-by-step traversal:

1. Start at root (value 3)

   • Current node: 3, Maximum seen so far: -1000000
   • Is 3 ≥ -1000000? Yes! → Node 3 is good, count = 1
   • Update maximum for children: mx = 3
   • Recursively visit left child (1) and right child (4)

2. Visit left child (value 1)

   • Current node: 1, Maximum seen so far: 3
   • Is 1 ≥ 3? No → Node 1 is not good, count stays 1
   • Keep maximum as 3 for its children
   • Recursively visit its left child (3)

3. Visit node with value 3 (left-left)

   • Current node: 3, Maximum seen so far: 3
   • Is 3 ≥ 3? Yes! → Node 3 is good, count = 2
   • No children to visit, backtrack

4. Back to root, now visit right child (value 4)

   • Current node: 4, Maximum seen so far: 3
   • Is 4 ≥ 3? Yes! → Node 4 is good, count = 3
   • Update maximum for children: mx = 4
   • Recursively visit its children (1 and 5)

5. Visit node with value 1 (right-left)

   • Current node: 1, Maximum seen so far: 4
   • Is 1 ≥ 4? No → Node 1 is not good, count stays 3
   • No children to visit, backtrack

6. Visit node with value 5 (right-right)

   • Current node: 5, Maximum seen so far: 4
   • Is 5 ≥ 4? Yes! → Node 5 is good, count = 4
   • No children to visit, backtrack

Final result: 4 good nodes (values 3, 3, 4, and 5)

The key insight illustrated here: each path maintains its own maximum value. When we visited the left subtree with node 1, we carried mx=3. When we visited the right subtree with node 4, we also started with mx=3. But after visiting node 4, its children received mx=4, which is why node 5 needed to be ≥ 4 to be considered good.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the number of nodes in the binary tree. The algorithm performs a depth-first search (DFS) traversal that visits each node exactly once. At each node, it performs constant time operations (comparison with mx, incrementing ans, and updating mx), so the total time complexity is linear with respect to the number of nodes.

Space Complexity: O(h) where h is the height of the binary tree. The space complexity is determined by the recursion call stack. In the worst case of a skewed tree (essentially a linked list), the height would be n, making the space complexity O(n). In the best case of a perfectly balanced tree, the height would be log(n), making the space complexity O(log n). The algorithm uses a constant amount of extra space for variables (ans and mx at each recursive call), but this doesn't change the overall space complexity which is dominated by the recursion stack depth.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Updating the Maximum Value Correctly

A frequent mistake is updating the max_so_far variable globally rather than maintaining it separately for each path. This leads to incorrect results when the tree has multiple branches.

Incorrect Approach:

def goodNodes(self, root: TreeNode) -> int:
    def dfs(node):
        if node is None:
            return
      
        # Wrong: Using and updating a shared maximum for all paths
        nonlocal global_max
        if node.val >= global_max:
            nonlocal good_node_count
            good_node_count += 1
            global_max = node.val  # This affects all branches!
      
        dfs(node.left)
        dfs(node.right)
  
    good_node_count = 0
    global_max = float('-inf')
    dfs(root)
    return good_node_count

Why it's wrong: When we traverse down one branch and update global_max, this incorrectly affects the evaluation of nodes in other branches. Each path from root should maintain its own maximum independently.

Correct Solution: Pass max_so_far as a parameter to each recursive call:

def dfs(node, max_so_far):
    if node is None:
        return
  
    if node.val >= max_so_far:
        nonlocal good_node_count
        good_node_count += 1
        max_so_far = node.val  # Local update for this path only
  
    dfs(node.left, max_so_far)   # Each call gets its own max
    dfs(node.right, max_so_far)

2. Forgetting to Count the Root Node

Another pitfall is using an initial maximum value that's too large, causing the root node to not be counted as good.

Incorrect:

# Starting with 0 or a positive number might exclude valid root nodes
dfs(root, 0)  # Wrong if root.val is negative

Correct:

# Use negative infinity to ensure root is always counted
dfs(root, float('-inf'))

3. Modifying the Maximum Before the Comparison

Some implementations mistakenly update the maximum value before checking if the current node is good:

Incorrect:

def dfs(node, max_so_far):
    if node is None:
        return
  
    # Wrong: Updating max before comparison
    max_so_far = max(max_so_far, node.val)
    if node.val >= max_so_far:  # This will always be true!
        nonlocal good_node_count
        good_node_count += 1

Correct:

def dfs(node, max_so_far):
    if node is None:
        return
  
    # Check first, then update
    if node.val >= max_so_far:
        nonlocal good_node_count
        good_node_count += 1
        max_so_far = node.val  # Update after counting

4. Using Strict Greater Than Instead of Greater Than or Equal

The problem states a node is good if no ancestor has a value greater than the current node's value. This means nodes with values equal to the maximum should also be counted.

Incorrect:

if node.val > max_so_far:  # Wrong: excludes nodes equal to max

Correct:

if node.val >= max_so_far:  # Correct: includes nodes equal to max