Even Odd Tree: Level-Order Validation

Given the root of a binary tree, determine whether it is an Even-Odd Tree. A binary tree is even-odd if it satisfies two rules at every level. At even-indexed levels (0, 2, 4, ...), every node value must be odd, and the values must be strictly increasing from left to right. At odd-indexed levels (1, 3, 5, ...), every node value must be even, and the values must be strictly decreasing from left to right. Return true if the tree meets both rules at every level, or false otherwise. This is LeetCode 1609: Even Odd Tree.

For example, given the tree [1, 10, 4, 3, 7, 9, 11], the answer is true. Level 0 has [1] (odd, trivially increasing). Level 1 has [10, 4] (both even, strictly decreasing). Level 2 has [3, 7, 9, 11] (all odd, strictly increasing).

Why this problem matters

Even Odd Tree combines two ideas that appear frequently in tree problems: level-order traversal and per-level validation. Many tree questions ask you to process nodes one level at a time and apply some rule. Zigzag traversal reverses direction at alternating levels. Right side view picks the last node per level. This problem checks parity and monotonicity per level. Once you recognize that the core is BFS with a level-by-level loop, the rest is applying the right constraints inside that loop.

The key insight

You do not need two separate passes or a complex data structure. A single BFS traversal, where you snapshot the queue size at the start of each level, gives you all the nodes at that level in left-to-right order. For each level, you just need to check two things: does every value have the correct parity (odd for even levels, even for odd levels), and is the sequence strictly monotonic in the required direction? If any node fails either check, return false immediately.

The trick for checking monotonicity is to track the previous value as you process nodes within a level. For even levels, each value must be greater than the previous. For odd levels, each value must be less than the previous. Initialize the previous value to 0 for even levels (since all valid values are positive and odd, any odd value will be greater than 0) and to float('inf') for odd levels (since any even value will be less than infinity).

The solution

from collections import deque

def is_even_odd_tree(root):
    if not root:
        return True
    queue = deque([root])
    level = 0
    while queue:
        level_size = len(queue)
        prev = 0 if level % 2 == 0 else float('inf')
        for _ in range(level_size):
            node = queue.popleft()
            val = node.val
            if level % 2 == 0:
                if val % 2 == 0 or val <= prev:
                    return False
            else:
                if val % 2 == 1 or val >= prev:
                    return False
            prev = val
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        level += 1
    return True

Here is what each part does:

• queue = deque([root]) seeds BFS with the root at level 0.
• level_size = len(queue) snapshots how many nodes belong to the current level before draining begins.
• prev = 0 if level % 2 == 0 else float('inf') initializes the comparison value. For even levels (expecting odd, increasing values), 0 works because all tree values are positive. For odd levels (expecting even, decreasing values), infinity works because any real value is smaller.
• The parity check (val % 2 == 0 on even levels, val % 2 == 1 on odd levels) catches values with the wrong parity immediately.
• The ordering check (val <= prev on even levels, val >= prev on odd levels) ensures strict monotonicity. Using <= and >= (rather than < and >) catches both equal values and wrong-direction values in a single comparison.
• prev = val updates the tracker after each node passes both checks.

Visual walkthrough

Trace BFS through the tree [1, 10, 4, 3, 7, 9, 11]. Watch how each level is processed and validated against the parity and ordering rules.

At every level, BFS processes nodes left to right. Level 0 has one odd node (1), which trivially satisfies both rules. Level 1 has two even nodes (10, 4) in strictly decreasing order. Level 2 has four odd nodes (3, 7, 9, 11) in strictly increasing order. All levels pass, so the tree is even-odd.

Complexity analysis

Every node is enqueued and dequeued exactly once, giving O(n) time. The queue holds at most one full level of nodes. In the worst case (a complete binary tree), the bottom level contains roughly n/2 nodes, so the space is O(n).

The building blocks

1. BFS level-by-level processing

The core template snapshots the queue size and drains exactly that many nodes per level. This is the same template used in level-order traversal, zigzag traversal, and right side view:

from collections import deque

def bfs_by_level(root):
    queue = deque([root])
    level = 0
    while queue:
        level_size = len(queue)
        for _ in range(level_size):
            node = queue.popleft()
            for child in [node.left, node.right]:
                if child:
                    queue.append(child)
        level += 1

2. Per-level constraint checking

Inside the inner loop, you validate each node against the rules for its level. The pattern of tracking a prev value and comparing each new value against it is reusable any time you need to verify monotonicity across a sequence.

Edge cases

• Empty tree (root is None): return true. There are no levels to violate the rules.
• Single node: the root is at level 0 (even). Its value must be odd. If it is even, return false.
• Equal adjacent values at a level: for example, level 1 has [4, 4]. The ordering must be strictly decreasing, so equal values fail. The >= check catches this.
• Correct parity but wrong ordering: for example, level 0 has [7, 3] (both odd, but decreasing instead of increasing). The ordering check catches this even though parity is fine.
• Large tree with failure at the deepest level: BFS will reach it. There is no early termination for depth, only for constraint violations.

From understanding to recall

You just traced through a BFS solution that checks parity and ordering at each level. The idea is clear right now. But will you remember whether even levels require increasing or decreasing order in a week? Will you recall the prev initialization trick without looking it up?

Understanding a pattern and reproducing it under pressure are different skills. Spaced repetition bridges that gap. You practice the BFS level-by-level template from memory, then layer on the constraint-checking pattern. First after a day, then three days, then a week. Each repetition reinforces the queue snapshot, the level counter, and the validation logic until it becomes automatic.

BFS level-by-level is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Binary Tree Level Order Traversal - The base BFS level-by-level template that this problem builds on
• Binary Tree Zigzag Level Order Traversal - Another level-by-level BFS variation that alternates direction per level
• Binary Tree Right Side View - BFS on trees with per-level extraction logic

Once you internalize the BFS level-by-level template, problems like Even Odd Tree become a matter of plugging in the right per-level validation. The template handles traversal; you supply the constraint.