Watch 10 video solutions for Count Good Nodes in Binary Tree, a medium level problem involving Tree, Depth-First Search, Breadth-First Search. This walkthrough by NeetCode has 141,872 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
[1, 10^5].[-10^4, 10^4].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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Depth First Search (DFS) | O(n) | O(h) | Preferred interview solution. Clean recursion and natural for path-based tree problems. |
| Iterative Breadth First Search (BFS) | O(n) | O(n) | Useful when avoiding recursion or when processing nodes level by level. |