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].This solution defines a helper function dfs that performs the depth-first search. It takes parameters for the current node and the maximum value encountered so far. It returns the total count of good nodes.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of nodes in the binary tree.
Space Complexity: O(h), where h is the height of the tree due to the recursion stack.
The C solution implements an iterative BFS using a custom queue structure. Each item in the queue stores a node and the maximum value along the path from the root to that node. The algorithm iterates over the queue, evaluating each node's value against the max value, updating good nodes count accordingly.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of nodes in the tree.
Space Complexity: O(w), where w is the maximum width of the tree.
| Approach | Complexity |
|---|---|
| Recursive Depth First Search (DFS) | Time Complexity: O(n), where n is the number of nodes in the binary tree. |
| Iterative Breadth First Search (BFS) | Time Complexity: O(n), where n is the number of nodes in the tree. |
Microsoft's Most Asked Question 2021 - Count Good Nodes in a Binary Tree - Leetcode 1448 - Python • NeetCode • 111,386 views views
Watch 9 more video solutions →Practice Count Good Nodes in Binary Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor