Problem Statement

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.

Link To the Problem

Intuition

A node is considered good if, on the path from the root to that node, there are no nodes with a greater value than it.

So, as we traverse the tree, we can keep track of the maximum value encountered so far along the path.
If the current node’s value is greater than or equal to this maximum, we count it as a “good” node.

Approach

We can solve this problem using Depth-First Search (DFS).

1. Start from the root and initialize the max_until_now as negative infinity.
2. At each node:
   • If node.val >= max_until_now, it’s a good node.
   • Update the maximum for the next recursive calls as max(max_until_now, node.val).
3. Recursively count the number of good nodes in the left and right subtrees.
4. The total number of good nodes is the sum of:
   • 1 (if the current node is good)
   • number of good nodes in the left subtree
   • number of good nodes in the right subtree.

Complexity

• Time Complexity:
  O(n), since we visit every node exactly once.

• Space Complexity:
  O(h), where h is the height of the tree (due to recursion stack).

  • Worst case (skewed tree): O(n)
  • Best case (balanced tree): O(\log n)

Code

# 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:

        def dfs(node, max_until_now):
            if not node:
                return 0

            res = 0
            if node.val >= max_until_now:
                res += 1

            new_max = max(max_until_now, node.val)
            res += dfs(node.left, new_max)
            res += dfs(node.right, new_max)

            return res

        return dfs(root, -float("inf"))