Skip to content
AI360Xpert
Back to Trees
Medium

Count Good Nodes in Binary Tree

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.

Examples

Input:root = [3,1,4,3,null,1,5]
Output:4
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.
Input:root = [3,3,null,4,2]
Output:3
Node 2 -> (3, 3, 2) is not good, because 3 is higher than it.
Input:root = [1]
Output:1
Root is considered as good.

Constraints

  • The number of nodes in the binary tree is in the range [1, 10^5].
  • -10^4 <= Node.val <= 10^4

DFS (Preorder Traversal)

Approach

Intuition: As we traverse down the tree from the root, we need to keep track of the maximum value we have seen so far along the current path. A node is "good" if its value is greater than or equal to this maximum value. Logic: 1. Initialize a helper DFS function that takes a node and the `maxValue` encountered so far on the path to this node. 2. Base case: If the node is null, return 0. 3. Check if the current node's value is greater than or equal to `maxValue`. If it is, this is a good node, so we count it as 1. Otherwise, it's 0. 4. Update the `maxValue` to be the maximum of the current `maxValue` and the current node's value. 5. Recursively call the DFS function for the left and right children, passing the updated `maxValue`. 6. Return the sum of the result for the current node, the left subtree, and the right subtree. 7. Initially, call the DFS function with the root and a `maxValue` of negative infinity (or the root's value).

Complexity Analysis

Time Complexity
O(n)
Space Complexity
O(h)

Every node in the tree is visited exactly once.

Solution.java
class Solution {    public int goodNodes(TreeNode root) {        return dfs(root, root.val);    }        private int dfs(TreeNode node, int maxSoFar) {        if (node == null) {            return 0;        }                int res = 0;        // Check if the current node is a good node        if (node.val >= maxSoFar) {            res = 1;        }                // Update the max value seen so far on this path        maxSoFar = Math.max(maxSoFar, node.val);                // Traverse left and right        res += dfs(node.left, maxSoFar);        res += dfs(node.right, maxSoFar);                return res;    }}