Practice/Meta/Leetcode 1609. Even Odd Tree

Leetcode 1609. Even Odd Tree

CodingOptional

Problem

Given the root of a binary tree, determine whether it satisfies specific alternating level constraints. The tree is considered valid if and only if it meets the following criteria:

• Even-indexed levels (level 0, 2, 4, ...): All node values must be odd integers, and the values must be in strictly increasing order from left to right.
• Odd-indexed levels (level 1, 3, 5, ...): All node values must be even integers, and the values must be in strictly decreasing order from left to right.

Return true if the tree satisfies these constraints, otherwise return false.

Requirements

1. Traverse the tree level by level (breadth-first traversal)
2. At each level, verify that all values match the required parity (odd or even)
3. At each level, verify that values follow the required ordering (strictly increasing or strictly decreasing)
4. Handle empty trees and single-node trees appropriately
5. Levels are 0-indexed starting from the root

Constraints

• The number of nodes in the tree is in the range [1, 100000]
• 1 ≤= Node.val ≤= 1000000
• Time complexity should be O(n) where n is the number of nodes
• Space complexity should be O(w) where w is the maximum width of the tree

Examples

Example 1:

Input: root = [1,10,4,3,null,7,9,12,8,6,null,null,2] Output: true Explanation: Level 0: [1] - all odd, no ordering issues (single element) Level 1: [10, 4] - all even, strictly decreasing (10 > 4) Level 2: [3, 7, 9] - all odd, strictly increasing (3 < 7 < 9) Level 3: [12, 8, 6, 2] - all even, strictly decreasing (12 > 8 > 6 > 2) All constraints are satisfied.

Example 2:

Input: root = [5,4,2,3,3,7] Output: false Explanation: Level 0: [5] - valid (odd) Level 1: [4, 2] - valid (even, decreasing) Level 2: [3, 3, 7] - invalid (contains duplicate 3, not strictly increasing)

Example 3:

Input: root = [2,3,5] Output: false Explanation: Level 0: [2] - invalid (even value at even-indexed level, should be odd)