Even Odd Tree

medium tree bfs

Problem

A binary tree is even-odd if at every even-indexed level all values are odd and strictly increasing left-to-right, and at every odd-indexed level all values are even and strictly decreasing left-to-right. Decide whether it is even-odd.

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

Outputtrue

Level 0: [1] odd ↑. Level 1: [10,4] even ↓. Level 2: [3,7,9] odd ↑. Level 3: [12,8,6,2] even ↓.

level-order (comma, 'null' for missing)

from collections import deque
def is_even_odd_tree(root):
    q = deque([root])
    level = 0
    while q:
        prev = None
        for _ in range(len(q)):
            n = q.popleft()
            if level % 2 == 0:
                if n.val % 2 == 0: return False
                if prev is not None and n.val <= prev: return False
            else:
                if n.val % 2 == 1: return False
                if prev is not None and n.val >= prev: return False
            prev = n.val
            if n.left: q.append(n.left)
            if n.right: q.append(n.right)
        level += 1
    return True

function isEvenOddTree(root) {
  const q = [root];
  let level = 0;
  while (q.length) {
    let prev = null, size = q.length;
    for (let k = 0; k < size; k++) {
      const n = q.shift();
      if (level % 2 === 0) {
        if (n.val % 2 === 0) return false;
        if (prev !== null && n.val <= prev) return false;
      } else {
        if (n.val % 2 === 1) return false;
        if (prev !== null && n.val >= prev) return false;
      }
      prev = n.val;
      if (n.left) q.push(n.left);
      if (n.right) q.push(n.right);
    }
    level++;
  }
  return true;
}

class Solution {
    public boolean isEvenOddTree(TreeNode root) {
        Deque<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        int level = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            Integer prev = null;
            for (int k = 0; k < size; k++) {
                TreeNode n = q.poll();
                if (level % 2 == 0) {
                    if (n.val % 2 == 0) return false;
                    if (prev != null && n.val <= prev) return false;
                } else {
                    if (n.val % 2 == 1) return false;
                    if (prev != null && n.val >= prev) return false;
                }
                prev = n.val;
                if (n.left != null) q.add(n.left);
                if (n.right != null) q.add(n.right);
            }
            level++;
        }
        return true;
    }
}

bool isEvenOddTree(TreeNode* root) {
    queue<TreeNode*> q; q.push(root);
    int level = 0;
    while (!q.empty()) {
        int size = q.size(), prev = -1;
        bool hasPrev = false;
        for (int k = 0; k < size; k++) {
            TreeNode* n = q.front(); q.pop();
            if (level % 2 == 0) {
                if (n->val % 2 == 0) return false;
                if (hasPrev && n->val <= prev) return false;
            } else {
                if (n->val % 2 == 1) return false;
                if (hasPrev && n->val >= prev) return false;
            }
            prev = n->val; hasPrev = true;
            if (n->left) q.push(n->left);
            if (n->right) q.push(n->right);
        }
        level++;
    }
    return true;
}

Explanation

The rules in this problem are all about levels, so the natural tool is a level-by-level BFS. On even levels values must be odd and strictly increasing left to right; on odd levels they must be even and strictly decreasing.

We process one level at a time using a queue, tracking the current level number. For each level we reset a prev value so we can compare neighbours within that row.

For every node we run two checks. The parity check: on an even level n.val must be odd, on an odd level it must be even. The order check: compared to prev, the value must be strictly greater on even levels and strictly smaller on odd levels. Any failure returns false right away.

If we finish all levels without a violation, the tree satisfies every rule and we return true. Children are pushed onto the queue as we go so the next level is ready.

Example: [1,10,4,3,null,7,9,12,8,6,null,null,2]. Level 0 is [1] (odd ↑), level 1 is [10,4] (even ↓), level 2 is [3,7,9] (odd ↑), level 3 is [12,8,6,2] (even ↓). Every rule holds, so the answer is true.

Time: O(n) Space: O(w)