Count Good Nodes in Binary Tree

Mediumtreedepth-first-searchrecursion
Category: Trees
Companies that ask this question:
AmazonMicrosoftFacebook
LeetCode →NeetCode →

Approach

Count Good Nodes in Binary Tree

Problem Statement

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

Input: root = [3,1,4,3,null,1,5]
Output: 4

Tree:
       3
      / \
     1   4
    /   / \
   3   1   5

Good nodes: 3 (root), 4 (3→4, no greater), 3 (3→1→3, no greater), 5 (3→4→5, no greater)
Bad nodes: 1 (3→1, 3 > 1), 1 (3→4→1, 4 > 1)

Example 2

Input: root = [3,3,null,4,2]
Output: 3

Tree:
     3
    /
   3
  / \
 4   2

Good nodes: 3 (root), 3 (3→3, equal counts), 4 (3→3→4, no greater)
Bad nodes: 2 (3→3→2, 3 > 2)

Example 3

Input: root = [1]
Output: 1

Intuition

A node is "good" if it's >= all ancestors in its path from root.

We need to track the maximum value seen so far on the path from root to current node.

For each node:

  • If node.val >= max_so_far → node is good
  • Update max_so_far = max(max_so_far, node.val)
  • Recursively check children with updated max_so_far

Pattern Recognition

This is a DFS with Path Context problem with:

  • Pre-order traversal (check node before children)
  • Pass down maximum value seen on path
  • Count good nodes while traversing

Approach

DFS with Max Tracking

  1. Helper Function: dfs(node, max_so_far)

    • Returns count of good nodes in subtree

  2. For Each Node:

    • Base case: if null, return 0
    • Check if current node is good: node.val >= max_so_far
    • Update max for children: new_max = max(max_so_far, node.val)
    • Recurse on both children with new_max
    • Return total count

  3. Initial Call: dfs(root, root.val) or dfs(root, -∞)

Why this works:

  • We maintain path context (max value seen)
  • Each node compares against its ancestors' max
  • DFS ensures we visit all nodes

Implementation

def goodNodes(root):
  def dfs(node, max_val):
    if not node:
      return 0

    # Count current node if it's good
    count = 1 if node.val >= max_val else 0

    # Update max for children
    new_max = max(max_val, node.val)

    # Add counts from subtrees
    count += dfs(node.left, new_max)
    count += dfs(node.right, new_max)

    return count

  return dfs(root, float('-inf'))

Edge Cases

  • Single node (always good)
  • All increasing path (all good)
  • All decreasing path (only root good)
  • Nodes with equal values (equal counts as good)
  • Negative values

Complexity Analysis

  • Time: O(n) where n = number of nodes

    • Visit each node once
    • O(1) work per node

  • Space: O(h) where h = height

    • Recursion call stack
    • O(log n) for balanced tree
    • O(n) for skewed tree

Solution

java
1class TreeNode {
2    int val;
3    TreeNode left;
4    TreeNode right;
5    TreeNode() {}
6    TreeNode(int val) { this.val = val; }
7    TreeNode(int val, TreeNode left, TreeNode right) {
8        this.val = val;
9        this.left = left;
10        this.right = right;
11    }
12}
13
14class Solution {
15    public int goodNodes(TreeNode root) {
16        return dfs(root, Integer.MIN_VALUE);
17    }
18
19    private int dfs(TreeNode node, int maxVal) {
20        if (node == null) {
21            return 0;
22        }
23
24        // Check if current node is good
25        int count = node.val >= maxVal ? 1 : 0;
26
27        // Update max value for children
28        int newMax = Math.max(maxVal, node.val);
29
30        // Count good nodes in subtrees
31        count += dfs(node.left, newMax);
32        count += dfs(node.right, newMax);
33
34        return count;
35    }
36}
37
Loading visualizer...