Count Good Nodes in Binary Tree - Solution & Explanation

Problem Overview: You are given the root of a binary tree. A node is considered good if no node on the path from the root to that node has a value greater than it. The task is to count how many such nodes exist in the tree.

Approach 1: Recursive Depth First Search (DFS) (Time: O(n), Space: O(h))

Traverse the tree using DFS while carrying the maximum value seen on the path from the root to the current node. When visiting a node, compare its value with the running maximum. If node.val >= max_so_far, the node is good and you increment the count. Update the running maximum with max(max_so_far, node.val) before continuing the recursion to the left and right children. Every node is visited exactly once, giving O(n) time complexity. The recursion stack uses O(h) space where h is the tree height (worst case O(n), balanced tree O(log n)). This approach naturally fits problems involving path-based constraints in a binary tree and is the most common interview solution using depth-first search.

Approach 2: Iterative Breadth First Search (BFS) (Time: O(n), Space: O(n))

The same idea can be implemented iteratively with a queue using breadth-first search. Store pairs in the queue: the current node and the maximum value seen along the path to that node. When dequeuing, check if the node value is greater than or equal to the stored maximum. If it is, count it as a good node and update the path maximum for its children. Push each child into the queue with the updated maximum value. Since each node is processed once, the traversal runs in O(n) time. The queue may hold up to an entire level of the tree, giving O(n) auxiliary space in the worst case.

Recommended for interviews: Recursive DFS is typically expected. It directly models the path constraint by passing the current maximum down the recursion. Interviewers often want to see that you recognize the pattern of carrying state along a root-to-node path. The BFS version demonstrates the same idea iteratively and is useful if recursion depth could become an issue.