Count Good Nodes in Binary Tree

Problem

Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.

Return the number of good nodes in the binary tree.

Example 1:

Input: root = [3,1,4,3,null,1,5]
Output: 4
Explanation: Nodes in blue are good.
Root Node (3) is always a good node.
Node 4 -> (3,4) is the maximum value in the path starting from the root.
Node 5 -> (3,4,5) is the maximum value in the path
Node 3 -> (3,1,3) is the maximum value in the path.

Example 2:

Input: root = [3,3,null,4,2]
Output: 3
Explanation: Node 2 -> (3, 3, 2) is not good, because "3" is higher than it.

Example 3:

Input: root = [1]
Output: 1
Explanation: Root is considered as good.

Constraints:

The number of nodes in the binary tree is in the range [1, 10^5].
Each node’s value is between [-10^4, 10^4].

Solution

Approach: DFS with Path Maximum

The key insight is to track the maximum value seen on the path from root to current node. A node is good if its value is >= this maximum.

Implementation

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        def dfs(node, max_so_far):
            if not node:
                return 0

            # Check if current node is good
            count = 1 if node.val >= max_so_far else 0

            # Update max for children
            new_max = max(max_so_far, node.val)

            # Count good nodes in subtrees
            count += dfs(node.left, new_max)
            count += dfs(node.right, new_max)

            return count

        return dfs(root, root.val)

Alternative (Using Instance Variable):

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        self.count = 0

        def dfs(node, max_val):
            if not node:
                return

            if node.val >= max_val:
                self.count += 1

            max_val = max(max_val, node.val)
            dfs(node.left, max_val)
            dfs(node.right, max_val)

        dfs(root, float('-inf'))
        return self.count

Complexity Analysis

Time Complexity: O(n), where n is the number of nodes. We visit each node once.
Space Complexity: O(h), where h is the height of the tree (recursion stack).

Key Insights

Path Maximum: We track the maximum value from root to current node, not the global maximum in the tree.
Good Node Definition: A node is good if no ancestor has a greater value, equivalently if node.val >= max_on_path.
Root is Always Good: The root has no ancestors, so it’s always good.
Propagate Maximum: We update and pass down the maximum to children, allowing each node to check itself.
DFS Traversal: We can use any DFS traversal (preorder, inorder, postorder) since we’re just counting nodes.