Count Good Nodes in Binary Tree

Problem

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

Example 1:

graph TD
    A(3)
    B(1)
    C(4)
    D(3)
    E(1)
    F(5)

    A:::blue --> B
    A:::blue --> C:::blue
    B --> D:::blue
    B ~~~ N1:::hidden
    C:::blue --> E
    C:::blue --> F:::blue

    classDef blue fill:#ADD8E6,stroke:#000,stroke-width:1px;
    classDef hidden display:none

1
2
3
4
5
6
7


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:

graph TD
    A(3)
    B(3)
    C(null)
    D(4)
    E(2)

    A:::blue --> B:::blue
    A:::blue ~~~ C:::hidden
    B:::blue --> D:::blue
    B:::blue --> E:::blue

    classDef blue fill:#ADD8E6,stroke:#000,stroke-width:1px;
    classDef hidden display:none

1
2
3


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:

1
2
3


Input: root = [1]
Output: 1
Explanation: Root is considered as good.

Solution

Method 1 - Preorder Traversal with Max Tracking

This problem can be solved using a recursive depth-first search (DFS).
As we traverse down the binary tree, we keep track of the maximum value encountered so far (max_val) along the path from the root to the current node.
A node is considered good if its value is greater than or equal to max_val.
For each node:
- Compare its value with max_val.
- If the node value is greater than or equal to max_val, count it as good.
- Update max_val to the maximum of the current max_val and the node’s value.
Recur for the left and right children of the node.
Aggregate the counts of good nodes.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution {
    public int goodNodes(TreeNode root) {
        return countGoodNodes(root, Integer.MIN_VALUE);
    }
    
    private int countGoodNodes(TreeNode node, int maxVal) {
        if (node == null) return 0;
        
        int ans = 0;
        if (node.val >= maxVal) ans = 1;
        
        maxVal = Math.max(maxVal, node.val);
        ans += countGoodNodes(node.left, maxVal);
        ans += countGoodNodes(node.right, maxVal);
        
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution:
    def goodNodes(self, root: Optional[TreeNode]) -> int:
        def count(node: Optional[TreeNode], max_val: int) -> int:
            if not node:
                return 0
            
            ans = 0
            if node.val >= max_val:
                ans = 1
            
            max_val = max(max_val, node.val)
            ans += count(node.left, max_val)
            ans += count(node.right, max_val)
            
            return ans
        
        return count(root, float('-inf'))

Complexity

⏰ Time complexity: O(n), where n is the number of nodes in the tree. As each node of the binary tree is visited exactly once.
🧺 Space complexity: O(h) is determined by the depth of recursion, where h is the height of the tree. In the worst case (skewed tree), this could be O(n).

Problem#

Examples#

Solution#

Method 1 - Preorder Traversal with Max Tracking#

Code#

Complexity#