Here is solutions for Count Good Nodes in Binary Tree.

1. Understand the problem

You are given the root of a binary tree.

• A node X in the tree is considered a “good node” if on the path from the root to X, there is no node with a value greater than X.

• Return the total number of good nodes in the tree.

Key interpretation:

• For each node, compare it with the maximum value seen so far from the root to that node.

• If node.val >= max_so_far, it is a good node.

2. Clarify constraints, asks 4 - 5 questions including edge cases.

1. Can the tree be empty?

• Yes -> Return 0.

1. Can node values be negative?

• Yes (range is typically [-10^4, 10^4]).

1. Can duplicate values appear?

• Yes -> >= still counts as good.

1. What is the tree size limit?

• Up to about 10^5 nodes → recursion depth risk.

1. What type of tree structure?

• Any (balanced, skewed, etc.).

3. Explore examples.

Example 1:

        3
       / \
      1   4
     /   / \
    3   1   5

Good nodes:

• 3 (root)

• 3 (left child of 1)

• 4

• 5

✅ Output: 4

4. Brainstorm 2 - 3 solutions, naive solution first and optimize later. Explain the key idea of each solution.

4.1. Naive Solution - Brute Force, Time O(N^2), Space O(N)

For each node:

• Traverse from root to that node

• Find the maximum value

• Check if node ≥ max

How:

• Use DFS to gather paths from root to every node

• For each path, check if last node is max

Complexity:

• Time: O(N^2)

• Space: O(N) recursion

4.2. Optimized DFS (Top-Down) — Time O(N), Space O(H)

At each node:

- If node.val >= max_so_far → count++

- Update: new_max = max(max_so_far, node.val)

- Recurse left and right

• Time: O(N).

• Space: O(H).

4.3. Iterative DFS / BFS — Time O(N), Space O(H)

• Same logic as Solution 2, but using:

• Stack (DFS) or Queue (BFS)

• Store (node, max_so_far) in stack

5. Implement solutions.

5.1. Depth First Search - Time O(N), Space O(H)

# 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, maxVal):
            if not node:
                return 0

            res = 1 if node.val >= maxVal else 0
            maxVal = max(maxVal, node.val)
            res += dfs(node.left, maxVal)
            res += dfs(node.right, maxVal)
            return res

        return dfs(root, root.val)

• Time: O(N)

• Space: O(H), worst case O(N).

5.2. Breadth First Search - Time O(N), Space O(N / 2)

• If node in low level > curr.val, count it as good nodes.

# 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:
        res = 0
        q = deque()

        q.append((root,-float('inf')))

        while q:
            node,maxval = q.popleft()
            if node.val >= maxval:
                res += 1

            if node.left:
                q.append((node.left,max(maxval,node.val)))

            if node.right:
                q.append((node.right,max(maxval,node.val)))

        return res

• Time: O(N)

• Space: O(N / 2)

5.3. Iterative DFS - Time O(N), Space O(H)

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

        stack = [(root, root.val)]
        count = 0

        while stack:
            node, max_so_far = stack.pop()

            if node.val >= max_so_far:
                count += 1

            new_max = max(max_so_far, node.val)

            if node.right:
                stack.append((node.right, new_max))
            if node.left:
                stack.append((node.left, new_max))

        return count

• Time: O(N)

• Space: O(H)

6. Dry run testcases.

1. Example 1

        3
       / \
      1   4
     /   / \
    3   1   5