#1448

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Count Good Nodes in Binary Tree

Count Good Nodes in Binary Tree identifies nodes exceeding all previous values along their path using DFS traversal techniques.

tree depth first search breadth first search binary tree

Problem Statement

Given a binary tree, a node is considered good if no node along the path from the root has a value greater than it. The task is to compute the total number of such good nodes in the tree.

For example, given root = [3,1,4,3,null,1,5], nodes like 3, 4, 5, and 3 are good because each is at least as large as any node along its path from the root. Return the total count of these nodes while handling up to 10^5 nodes efficiently.

Examples

Example 1

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.

Example 2

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

Output: 3

Node 2 -> (3, 3, 2) is not good, because "3" is higher than it.

Example 3

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].
Each node's value is between [-10^4, 10^4].

Solution Approach

Depth-First Search with Path Maximum

Use DFS to traverse the tree recursively, passing along the maximum value encountered so far. At each node, compare its value with the current path maximum to decide if it's good, and update the maximum for child nodes.

Breadth-First Search with Queue Tracking

Perform BFS using a queue where each element stores the node and the maximum value along the path. At each level, check if the node is good relative to the path maximum and update accordingly, ensuring all nodes are visited exactly once.

Iterative DFS using Stack

Simulate the DFS traversal with a stack storing pairs of nodes and current path maximums. Pop each node, check if it's good, update the maximum, and push its children, avoiding recursion and stack overflow for deep trees.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each node is visited once. Space complexity is O(h) for DFS recursion or stack, where h is the tree height, and O(n) for BFS queue in the worst case.

What Interviewers Usually Probe

Check if candidates correctly track the maximum along the path.
Notice if they handle edge cases with negative or duplicate values.
See if they choose DFS or BFS and justify stack versus queue use.

Common Pitfalls or Variants

Common pitfalls

Failing to update the path maximum when descending to child nodes.
Counting nodes incorrectly when values equal the current path maximum.
Using recursion without considering deep trees causing stack overflow.

Follow-up variants

Count nodes where the path maximum must be strictly less than the current node.
Return the list of good node values instead of just the count.
Apply the same path-max check in an N-ary tree instead of a binary tree.

FAQ

What defines a good node in Count Good Nodes in Binary Tree?

A node is good if no node in the path from the root has a value greater than the node itself.

Should I use DFS or BFS for this problem?

Either works; DFS is natural for recursion with path maximums, while BFS uses a queue to track max values at each node.

How does path maximum affect counting nodes?

The path maximum ensures that only nodes that are greater than or equal to all ancestors are counted as good.

Can values be negative or zero?

Yes, nodes may have values in [-10^4, 10^4], and the algorithm must compare each value correctly.

What is the main failure mode for this problem?

Common failure occurs when the algorithm does not update or carry forward the path maximum correctly, miscounting good nodes.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

# 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(root: TreeNode, mx: int):
            if root is None:
                return
            nonlocal ans
            if mx <= root.val:
                ans += 1
                mx = root.val
            dfs(root.left, mx)
            dfs(root.right, mx)

        ans = 0
        dfs(root, -1000000)
        return ans

Continue Practicing

#1457 pseudo palindromic paths in a binary tree #1361 validate binary tree nodes #1315 sum of nodes with even valued grandparent