Tech Blogs LLD SDE Playbook DSA

Count Good Nodes In Binary Tree

Medium Top 250
Associated Patterns
Trees
Interviewed At (Company Tags)
GoogleAmazonMicrosoftMeta
External Reference View on LeetCode

Problem Description

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.val.

Return the number of good nodes in the binary tree.

Examples

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 (3) under (1) is a good node because 3 >= [3,1]. Node (4) is a good node because 4 >= [3]. Node (5) is a good node because 5 >= [3,4]. Node (1) under (4) is not a good node because 1 is less than 4.

Example 2:

Input: root = [3,3,null,4,2] Output: 3 Explanation: Node (2) is not good because 2 is less than 3. Node (4) is good because 4 >= [3,3].

Constraints

  • The number of nodes in the tree is in the range [1, 10⁵].
  • Each node’s value is between [-10⁴, 10⁴].

DFS with Maximum Path Value Tracking

To determine if a node X is good, we need to compare its value with the maximum value seen on the path from the root to X. We can use Depth-First Search (DFS):

  1. Write a helper function dfs(node, maxVal) where maxVal is the highest node value encountered so far along the path.
  2. If node is null, return 0.
  3. Check if node.val >= maxVal. If so, this is a good node; we increment our good node count by 1 and update maxVal = node.val. Otherwise, our count is 0.
  4. Recursively count good nodes in the left child (dfs(node.left, maxVal)) and right child (dfs(node.right, maxVal)).
  5. Return the total count: isGood + leftGoodCount + rightGoodCount.

Solution 1: DFS Path Maximum Tracker

Traverse tree nodes, carrying the maximum value seen on the current path down to children.

/**
 * 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 {
    public int goodNodes(TreeNode root) {
        return dfs(root, Integer.MIN_VALUE);
    }

    private int dfs(TreeNode node, int maxVal) {
        if (node == null) return 0;

        int count = 0;
        if (node.val >= maxVal) {
            count = 1; // good node found
            maxVal = node.val; // update path maximum
        }

        count += dfs(node.left, maxVal);
        count += dfs(node.right, maxVal);
        return count;
    }
}
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def goodNodes(self, root: TreeNode) -> int:
        
        def dfs(node: Optional[TreeNode], max_val: int) -> int:
            if not node:
                return 0
                
            count = 0
            if node.val >= max_val:
                count = 1
                max_val = node.val  # update path maximum
                
            count += dfs(node.left, max_val)
            count += dfs(node.right, max_val)
            return count

        return dfs(root, float('-inf'))
#include <algorithm>
#include <climits>

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
private:
    int dfs(TreeNode* node, int maxVal) {
        if (!node) return 0;

        int count = 0;
        if (node->val >= maxVal) {
            count = 1;
            maxVal = node->val;
        }

        count += dfs(node->left, maxVal);
        count += dfs(node->right, maxVal);
        return count;
    }

public:
    int goodNodes(TreeNode* root) {
        return dfs(root, INT_MIN);
    }
};

Complexity Analysis

  • Time Complexity: O(n) since we visit every node in the binary tree exactly once.
  • Space Complexity: O(h) auxiliary space where h is the tree height, representing the recursion stack depth.

← All Problems