Skip to main content

Count Good Nodes Along Root Paths

easy
Binary TreeDepth First SearchTreeDfs Recursive
Asked atGoogleAmazonMicrosoftLinkedin

Problem Description

A node in a binary tree is considered **good** if, on the path from the root down to that node, no ancestor has a strictly greater value than the node's own value.

Given the root of a binary tree, return the total number of good nodes.

**Example 1:**
```
Input: root = [5, 3, 8, 3, 4, 7, 9]
Output: 5
```
Explanation: Nodes 5 (root, always good), 8, 3 (right child, equal to parent), 4, 9 are good. Node 3 (left child of 5) and 7 are also good — trace the max along each path.

**Example 2:**
```
Input: root = [10, 5, 15, 3, 7, null, 20]
Output: 4
```
Explanation: Nodes 10, 15, 20, and 7 are good. Node 5 is not (parent is 10). Node 3 is not (ancestor 10 exists).

Constraints

  • The number of nodes in the tree is in the range [1, 10000].
  • Node values are integers in the range [-10000, 10000].

Follow-up

Can you modify the solution to instead return the list of values of all good nodes in pre-order?

Hints

Try the problem first. If you get stuck, you can reveal hints one at a time.

Solution

Leaderboard

No entries yet for python.

Be the first — submit an accepted solution.