Problem Statement

Given a binary tree, return true if it is an Even-Odd tree. Otherwise, return false.

The Even-odd tree must follow below two rules:

1. At every even-indexed level (starting from 0), all node values must be odd and arranged in strictly increasing order from left to right.
2. At every odd-indexed level, all node values must be even and arranged in strictly decreasing order from left to right.

Examples

Example 1

• Input:

    1
   / \
  10  4
 / \
3   7

• Expected Output: true
• Justification: The tree follows both conditions for each odd and even level. So, it is an odd-even tree.

Example 2

Input:

    5
   / \
  9   3
 /     \
12      8

• Expected Output: false
• Justification: Level 1 has Odd values 9 and 3 in decreasing order, but it should have even values. So, the tree is not an odd-even tree.

Example 3

• Input:

    7
   / \
  10  2
 / \
12  8

• Expected Output: false
• Justification: At level 2 (even-indexed), the values are 12 and 8, which are even, but they should have odd values. So, the tree is not an odd-even tree.

Constraints:

• The number of nodes in the tree is in the range [1, 10⁵].
• 1 <= Node.val <= 10⁶

Try it yourself

Try solving this question here: