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.

&nbsp;
Example 1:

Input: root = [1,10,4,3,null,7,9,12,8,6,null,null,2]
Output: true
Explanation: The node values on each level are:
Level 0: [1]
Level 1: [10,4]
Level 2: [3,7,9]
Level 3: [12,8,6,2]
Since levels 0 and 2 are all odd and increasing and levels 1 and 3 are all even and decreasing, the tree is Even-Odd.


Example 2:

Input: root = [5,4,2,3,3,7]
Output: false
Explanation: The node values on each level are:
Level 0: [5]
Level 1: [4,2]
Level 2: [3,3,7]
Node values in level 2 must be in strictly increasing order, so the tree is not Even-Odd.


Example 3:

Input: root = [5,9,1,3,5,7]
Output: false
Explanation: Node values in the level 1 should be even integers.


&nbsp;
Constraints:


	The number of nodes in the tree is in the range [1, 105].
	1 &lt;= Node.val &lt;= 106


from collections import deque
# O(n) || O(h); where h is the height of the tree

class Solution:
    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return False

        level = 0
        evenOddLevel = {0:1, 1:0}
        queue = deque([root])

        while queue:
            prev = 0
            for _ in range(len(queue)):
                currNode = queue.popleft()
                comparison = {0:prev < currNode.val, 1:prev > currNode.val}
                if currNode.val % 2 != evenOddLevel[level % 2]:
                    return False
                else:
                    if prev != 0 and comparison[level % 2]:
                        prev = currNode.val
                    elif prev == 0:
                        prev = currNode.val
                    else:
                        return False

                if currNode.left:
                    queue.append(currNode.left)

                if currNode.right:
                    queue.append(currNode.right)

            level += 1

        return True
class Solution {
    public boolean isEvenOddTree(TreeNode root) {
        Queue<TreeNode> qu = new LinkedList<>();
        qu.add(root);
        boolean even = true; // maintain check for levels
        while(qu.size()>0){
            int size = qu.size();
            int prev = (even)?0:Integer.MAX_VALUE; // start prev with 0 to check strictly increasing and Integer_MAX_VALUE to check strictly decreasing 
            while(size-->0){
            TreeNode rem = qu.remove();
                if(even){
                    if(rem.val%2==0 || rem.val<=prev){ // false if value at even level is even or not strictly increasing 
                        return false;
                    }
                }else{
                    if(rem.val%2!=0 || rem.val>=prev){// false if value at odd level is odd or not strictly decreasing
                        return false;
                    }
                }
                if(rem.left!=null){
                    qu.add(rem.left); 
                }
                if(rem.right!=null){
                    qu.add(rem.right);
                }
                prev=rem.val;   //update previous
              
            }
              even = !even; //change level
        } 
        return true;
    }
}
class Solution {
public:
    bool isEvenOddTree(TreeNode* root) {
        queue<TreeNode*>q;
        vector<vector<int>>ans;
        if(root==NULL) return true;
        q.push(root);
        int j=0;
        while(q.empty()!=true)
        { vector<int>v;
            int n=q.size();
            for(int i=0;i<n;i++)
            { TreeNode* t=q.front();q.pop();
                v.push_back(t->val);
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }
         if(j%2==0)
         {
             for(int k=0;k<v.size()-1;k++)
             {
                 if(v[k]%2==0)
                     return false;
                 if(v[k]>=v[k+1])
                     return false;
             }
             if(v[v.size()-1]%2==0)
                 return false;
         }
         else
         {
              for(int k=0;k<v.size()-1;k++)
             {
                 if(v[k]%2==1)
                     return false;
                 if(v[k]<=v[k+1])
                     return false;
             }
             if(v[v.size()-1]%2==1)
                 return false;
         }
         j++;
            ans.push_back(v);
        }
        return true;
    }
};
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isEvenOddTree = function(root) {
    let queue = [root];
    let steps = 0;

    while(queue.length>0){
        const currLength = queue.length;
        let nextQueue=[];

        for(let i=0; i<currLength;i++){
            const node = queue[i];
            if(steps%2 !== 0){
                if((i<currLength-1 && node.val<=queue[i+1].val) || node.val%2 !== 0){
                    return false;
                }
            }else if((i<currLength-1 && node.val>=queue[i+1].val)|| node.val%2 === 0){
                return false;
            }
            if(node.left) nextQueue.push(node.left);
            if(node.right) nextQueue.push(node.right);
        }
        queue = nextQueue;
        steps++;
    }

    return true;
};
Even Odd Tree