All problems

Hopscotch Trail

Easy · tree dfs

A garden is laid out as a binary tree of stepping stones. The first stone is the root, and each stone leads on to at most two other stones, one on the left and one on the right. Every stone has a whole number painted on it.

A trail starts on the first stone and keeps stepping to a stone further along until it reaches a stone that leads nowhere (a leaf). A trail is a hopscotch trail if its stones alternate between odd and even numbers all the way: no two neighbouring stones on the trail may both be odd or both be even. The first stone may be either.

Return true if the garden contains at least one hopscotch trail, and false otherwise. A garden with no stones has no trail.

Examples

Example 1

Input: root = [5, 2, 8, 7, 4]

Output: true

The trail 5, 2, 7 goes odd, even, odd, and 7 is a leaf.

Example 2

Input: root = [3, 5, 7, 1]

Output: false

Every stone is odd, so any step from one stone to the next repeats the same kind of number.

Example 3

Input: root = [4]

Output: true

A single stone is already a complete trail.

Constraints