1609 · Even Odd Tree

A level-order traversal used as a validator rather than a collector. Two rules apply per level, both keyed off whether the level index is even or odd, and the traversal can bail out the instant either one breaks.

1 — The two rules

Levels are 0-indexed from the root. Then:

• Even levels (0, 2, 4 …): every value must be odd, and values must be strictly increasing left to right.
• Odd levels (1, 3, 5 …): every value must be even, and values must be strictly decreasing left to right.

Two things trip people up here. The first is the inversion — even levels hold odd values, not even ones — which reads like a typo in the problem statement and is not. The second is strict: equal neighbours are a violation, so the comparison must be <= / >= when testing for failure, never < / >.

2 — A valid tree

root = [1,10,4,3,null,7,9,12,8,6,null,null,2]. Level 0 is [1]; level 1 is [10, 4]; level 2 is [3, 7, 9]; level 3 is [12, 8, 6, 2].

int lvl = 0;while (!q.isEmpty()) {    int sz = q.size();    boolean even = lvl % 2 == 0;    int prev = even ? Integer.MIN_VALUE : Integer.MAX_VALUE;    for (int i = 0; i < sz; i++) {        if (nd.val % 2 == (even ? 0 : 1)) return false;        if (even ? nd.val <= prev : nd.val >= prev) return false;        prev = nd.val;    }    lvl++;}return true;

Note that the ordering rule applies across the whole level, not within each parent's pair of children — 3, 7, 9 spans two different parents and still has to increase. That is why this must be a level-order traversal and not a recursive one: only BFS naturally hands you a level in left-to-right order.

3 — A violation

Level 2 here is [3, 3] — both odd, so the parity rule passes, but they are equal.

int lvl = 0;while (!q.isEmpty()) {    int sz = q.size();    boolean even = lvl % 2 == 0;    int prev = even ? Integer.MIN_VALUE : Integer.MAX_VALUE;    for (int i = 0; i < sz; i++) {        if (nd.val % 2 == (even ? 0 : 1)) return false;        if (even ? nd.val <= prev : nd.val >= prev) return false;        prev = nd.val;    }    lvl++;}return true;

Strictly increasing means the second 3 fails, and the traversal stops immediately without examining the rest of the tree. Using < where you needed <= is the single most common way to fail this problem, and duplicate neighbours are the only input that exposes it.

4 — Complexity and edge cases

• Time: O(n) worst case, and much less on invalid input, since the first violation ends the scan.
• Space: O(w) for the queue.
• The sentinel matters: seed prev with Integer.MIN_VALUE on even levels and Integer.MAX_VALUE on odd ones, so the first node on a level always passes. Reusing one sentinel for both breaks one of the two directions.
• Values are at least 1, so there are no negatives to reason about — but do not rely on that if you adapt this elsewhere.
• A single node is valid exactly when its value is odd: it is level 0, and there is nothing to compare it against.
• Check parity before order, or don't — either works, since any violation returns false. Checking parity first tends to read better.

5 — Reference implementation

public boolean isEvenOddTree(TreeNode root) {
    Deque<TreeNode> q = new ArrayDeque<>();
    q.add(root);
    int lvl = 0;
    while (!q.isEmpty()) {
        int sz = q.size();
        boolean even = lvl % 2 == 0;
        int prev = even ? Integer.MIN_VALUE : Integer.MAX_VALUE;
        for (int i = 0; i < sz; i++) {
            TreeNode nd = q.poll();
            // even level -> odd values; odd level -> even values
            if (nd.val % 2 == (even ? 0 : 1)) return false;
            // STRICT monotonicity — note <= and >=
            if (even ? nd.val <= prev : nd.val >= prev) return false;
            prev = nd.val;
            if (nd.left  != null) q.add(nd.left);
            if (nd.right != null) q.add(nd.right);
        }
        lvl++;
    }
    return true;
}