All problems

Non-Decreasing Root Paths

Easy · tree dfs

You are given the root of a binary tree. A root-to-leaf path starts at the root and follows child links down to a leaf, a node with no children. A tree with only a root has exactly one path: the root on its own.

Call a path non-decreasing if, reading its values from the root downwards, no value is smaller than the one before it. Equal neighbours are fine.

Return the number of root-to-leaf paths in the tree that are non-decreasing. An empty tree has no paths, so return 0.

Examples

Example 1

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

Output: 2

The paths are 3 -> 3 -> 1, 3 -> 3 -> 4 and 3 -> 5 -> 6. The first one drops from 3 to 1, so only the other two count.

Example 2

Input: root = [5, 4, 3]

Output: 0

Both paths go down in value straight away: 5 -> 4 and 5 -> 3.

Example 3

Input: root = []

Output: 0

There are no paths in an empty tree.

Constraints