Even Odd Tree

Explanation & Solution

Practice Problem

Description

A binary tree is named Even-Odd if it meets the following conditions:

The root of the binary tree is at level index 0, its children are at level index 1, their children are at level index 2, etc.
For every even-indexed level, all nodes at the level have odd integer values in strictly increasing order (from left to right).
For every odd-indexed level, all nodes at the level have even integer values in strictly decreasing order (from left to right).

Given the root of a binary tree, return true if the binary tree is Even-Odd, otherwise return false.

Examples

Example 1:

```tree

[1, 10, 4, 3, null, 7, 9, 12, 8, 6, null, null, 2]

Input:root = [1, 10, 4, 3, null, 7, 9, 12, 8, 6, null, null, 2]

null

Output: true

Explanation:

Level 0: [1] — odd values, strictly increasing ✓
Level 1: [10, 4] — even values, strictly decreasing ✓
Level 2: [3, 7, 9] — odd values, strictly increasing ✓
Level 3: [12, 8, 6, 2] — even values, strictly decreasing ✓

Example 2:

```tree

[5, 4, 2, 3, 3, 7]

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

Output: false

Explanation: Level 2 has values [3, 3, 7]. The values are not strictly increasing (3 is not less than 3).

Example 3:

```tree

[5, 9, 1, 3, 5, 7]

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

Output: false

Explanation: Level 1 has values [9, 1]. They are odd, but odd-indexed levels must have even values.

Constraints

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

Approach

Tree Breadth-First Search pattern

1. Handle Empty Tree

If root is null, return true (vacuously true)

2. Initialize BFS

Create a queue with the root node
Track the current level index starting at 0

3. Process Level by Level

For each level, track the previous value (prev) to check ordering
For each node in the current level:
Even-indexed level (level % 2 === 0):
Check that the value is odd — if even, return false
Check that values are strictly increasing — if val <= prev, return false
Odd-indexed level (level % 2 === 1):
Check that the value is even — if odd, return false
Check that values are strictly decreasing — if val >= prev, return false
Update prev to the current value
Enqueue left and right children

4. Increment Level

After processing all nodes in a level, increment level

5. Return True

If BFS completes without returning false, the tree satisfies all conditions

Key Insight

BFS naturally processes the tree level by level, which is exactly what this problem requires
At each level we verify two properties: parity (odd/even) and ordering (increasing/decreasing)

Time

O(n)every node is visited once

Space

O(n)the queue may hold up to an entire level of nodes

Visualization

Input:

DFS Traversal[1, 10, 4, 3, 7, 9, 12, 8, 6, 2]

output0

Press play to start DFS traversal

CurrentIn stackComplete

19 steps

Solution Code

Maximum Width of Binary Tree

Find Largest Value in Each Tree Row