Even odd tree

XXX. Even-Odd Tree

Tree

Breadth-First Search

Problem Statement:

Determine if a binary tree is an "Even-Odd Tree." A binary tree is an even-odd tree if:

• Nodes on even-indexed levels contain odd values in strictly increasing order.
• Nodes on odd-indexed levels contain even values in strictly decreasing order.

Algorithm:

1. Perform a level-order traversal using a queue.
2. For each level:
   • Check whether the node values satisfy the even-odd constraints.
   • Maintain the previous value to ensure strictly increasing or decreasing order.
3. Return true if all levels satisfy the constraints; otherwise, return false.

Complexity:

Time Complexity: O(n), where n is the number of nodes in the tree.
Space Complexity: O(w), where w is the maximum width of the tree (due to the queue).

Java Implementation:

public boolean isEvenOddTree(TreeNode root) {
    Queue q = new ArrayDeque<>();
    int levelIdx = 0;

    q.add(root);

    while (!q.isEmpty()) {
        int size = q.size();
        Integer prev = null;

        for (int i = 0; i < size; i++) {
            TreeNode curr = q.poll();

            if (levelIdx % 2 == 0) {
                if (curr.val % 2 == 0 || (prev != null && curr.val <= prev)) return false;
            } else {
                if (curr.val % 2 == 1 || (prev != null && curr.val >= prev)) return false;
            }

            if (curr.left != null) q.add(curr.left);
            if (curr.right != null) q.add(curr.right);

            prev = curr.val;
        }

        levelIdx++;
    }

    return true;
}
                

Python Implementation:

from collections import deque

def is_even_odd_tree(root):
    q = deque([root])
    level_idx = 0

    while q:
        size = len(q)
        prev = None

        for _ in range(size):
            curr = q.popleft()

            if level_idx % 2 == 0:
                if curr.val % 2 == 0 or (prev is not None and curr.val <= prev):
                    return False
            else:
                if curr.val % 2 == 1 or (prev is not None and curr.val >= prev):
                    return False

            if curr.left:
                q.append(curr.left)
            if curr.right:
                q.append(curr.right)

            prev = curr.val

        level_idx += 1

    return True
                

C++ Implementation:

#include 
#include 
using namespace std;

bool isEvenOddTree(TreeNode* root) {
    queue q;
    q.push(root);
    int levelIdx = 0;

    while (!q.empty()) {
        int size = q.size();
        int prev = (levelIdx % 2 == 0) ? INT_MIN : INT_MAX;

        for (int i = 0; i < size; i++) {
            TreeNode* curr = q.front(); q.pop();

            if (levelIdx % 2 == 0) {
                if (curr->val % 2 == 0 || curr->val <= prev) return false;
            } else {
                if (curr->val % 2 == 1 || curr->val >= prev) return false;
            }

            if (curr->left) q.push(curr->left);
            if (curr->right) q.push(curr->right);

            prev = curr->val;
        }

        levelIdx++;
    }

    return true;
}