Count Good Nodes in Binary Tree
MedPrompt
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:
- The number of nodes in the binary tree is in the range
[1, 10^5]. - Each node's value is between
[-10^4, 10^4].
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses a Depth-First Search (DFS) traversal. As we traverse down the tree, we maintain a list of the values of the nodes in the current path from the root. For each node, we check if it's 'good' by finding the maximum value in the path list and comparing it with the node's own value.
Algorithm
- Initialize a global counter for good nodes to 0.
- Create a recursive helper function, e.g.,
dfs(node, pathList). - The initial call is
dfs(root, new ArrayList<>()). - Inside the helper function, if the
nodeis null, return. - Find the maximum value in the
pathList. If the list is empty (for the root), the max can be consideredInteger.MIN_VALUE. - If
node.valis greater than or equal to this maximum, increment the global counter. - Add
node.valto thepathListto extend the path for its children. - Make recursive calls:
dfs(node.left, pathList)anddfs(node.right, pathList). - After the recursive calls return, backtrack by removing the last element from
pathList.
Walkthrough
In this method, we employ a recursive helper function that takes the current node and a list representing the path from the root to the node's parent.
When visiting a node, we first iterate through the entire path list to find the maximum value among its ancestors. If the current node's value is greater than or equal to this maximum, we count it as a good node. After the check, we add the current node's value to the path list and make recursive calls for its children.
Crucially, after the recursive calls for the children return (i.e., after exploring the entire subtree), we must remove the current node's value from the path list. This backtracking step ensures that the path list is correct for sibling nodes and their subtrees.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */import java.util.ArrayList;import java.util.List; class Solution { int goodNodesCount = 0; public int goodNodes(TreeNode root) { if (root == null) return 0; // For the root, the path is empty, so any value is good. dfs(root, new ArrayList<>()); return goodNodesCount; } private void dfs(TreeNode node, List<Integer> path) { if (node == null) { return; } // Check if the current node is good int maxInPath = Integer.MIN_VALUE; for (int val : path) { if (val > maxInPath) { maxInPath = val; } } if (node.val >= maxInPath) { goodNodesCount++; } // Recurse for children path.add(node.val); dfs(node.left, path); dfs(node.right, path); // Backtrack: remove the current node from the path path.remove(path.size() - 1); }}Complexity
Time
O(N * H), where N is the number of nodes and H is the height of the tree. We visit each of the N nodes. At each node, we iterate through the current path to find the maximum value. The path length can be up to H. In the worst case of a skewed tree, H can be N, leading to O(N^2) complexity.
Space
O(H), where H is the height of the tree. This space is used for the recursion stack and to store the `pathList`. In the worst case of a skewed tree, this becomes O(N).
Trade-offs
Pros
Conceptually simple as it directly models the problem of checking the full path for each node.
Cons
Highly inefficient due to redundant computations. The maximum value of the path is recalculated at every node.
Higher time complexity compared to the optimal solution.
Requires careful implementation of backtracking.
Solutions
Solution
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private int ans = 0 ; public int goodNodes ( TreeNode root ) { dfs ( root , - 100000 ); return ans ; } private void dfs ( TreeNode root , int mx ) { if ( root == null ) { return ; } if ( mx <= root . val ) { ++ ans ; mx = root . val ; } dfs ( root . left , mx ); dfs ( root . right , mx ); } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.