Unchallenged Nodes

MediumTrees

Problem

In a ranking tree, a node is unchallenged if no node on the path from the root down to it (excluding itself) has a strictly greater value. The root is always unchallenged.

Given the root, return the number of unchallenged nodes.

Example 1

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

3 (root), 4, 5 and the lower 3 (path 3 → 1 → 3) are unchallenged.

Example 2

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

2 is challenged by both 3s above it.

Constraints

  • 0 ≤ number of nodes ≤ 10^5
  • -10^4 ≤ node.val ≤ 10^4

Hint

Show the first hint

To decide about a node you only need one number from the whole path above it. Which one?

Walkthrough

How to approach it

01Clarify before coding

  • Is equality allowed? Yes: a node equal to the maximum above it is still unchallenged.
  • Do siblings or cousins matter? No, only ancestors.
  • Empty tree? 0.

02Brute force

For each node, walk the whole path from the root and compare against every ancestor.

Cost: O(n · h), up to O(n²) for a chain.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.