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⁶

Solution

To solve this problem, we can perform a level-order traversal (BFS) of the binary tree. During this traversal, we will keep track of the current level index to check whether it is even or odd. For each level, we will store the node values and verify the required conditions:

• If the level is even, the values should be odd and in strictly increasing order.
• If the level is odd, the values should be even and in strictly decreasing order.

This approach is efficient because it allows us to traverse each node once and check the conditions in a single pass. By maintaining a queue for BFS and lists for each level's values, we can ensure that all conditions are checked accurately.

Step-by-step Algorithm

1. Initialize a queue for level-order traversal and add the root node to it.
2. Initialize a variable level to 0 to keep track of the current level.
3. While the queue is not empty:
   • Determine the number of nodes at the current level (size).
   • Create an empty list (values) to store the values of the nodes at the current level.
   • For each node in the current level:
     • Remove the node from the queue.
     • Add its value to the values list.
     • If the node has a left child, add it to the queue.
     • If the node has a right child, add it to the queue.
   • Check the values collected at the current level:
     • If the level is even:
       • Ensure all values are odd and strictly increasing.
     • If the level is odd:
       • Ensure all values are even and strictly decreasing.
   • If the values do not meet the required conditions, return false.
   • Increment the level by 1.
4. Return true if all levels meet the required conditions.

Algorithm Walkthrough

Input Tree:

    1
   / \
  10  4
 / \
3   7

Steps:

1. Initialization:

   • Queue: [1]
   • Level: 0

2. Level 0:

   • Size: 1
   • Values: []
   • Process node 1:
     • Queue: []
     • Values: [1]
     • Add left child (10) to the queue
     • Add right child (4) to the queue
   • Check values for even level:
     • Values: [1] (all odd and strictly increasing)
   • Increment level: 1

3. Level 1:

   • Size: 2
   • Values: []
   • Process node 10:
     • Queue: [4]
     • Values: [10]
     • Add left child (3) to the queue
     • Add right child (7) to the queue
   • Process node 4:
     • Queue: [3, 7]
     • Values: [10, 4]
   • Check values for odd level:
     • Values: [10, 4] (all even and strictly decreasing)
   • Increment level: 2

4. Level 2:

   • Size: 2
   • Values: []
   • Process node 3:
     • Queue: [7]
     • Values: [3]
   • Process node 7:
     • Queue: []
     • Values: [3, 7]
   • Check values for even level:
     • Values: [3, 7] (all odd and strictly increasing)
   • Increment level: 3

5. Completion:

   • Queue is empty, all levels meet the required conditions.
   • Return true.

Code