All problems

Count Good Nodes in Binary Tree

Medium · tree dfs

You are given the root of a binary tree of integers. Call a node good if, on the path from the root down to that node (including both ends), no node has a value greater than the node's own value. In other words, nothing above it is bigger. Equal values do not spoil it.

The root has nothing above it, so it is always good. Return the number of good nodes in the tree.

Examples

Example 1

Input: root = [5, 2, 8, 6, 1, 9, 3]

Output: 4

The good nodes are 5 (the root), 8, 6 and 9. The node 6 sits under 5 and 2, and neither is bigger than 6. The nodes 2, 1 and 3 each have a bigger value above them.

Example 2

Input: root = [4, 4, 4]

Output: 3

Equal values do not count against a node, so all three are good.

Example 3

Input: root = [7]

Output: 1

Constraints