Even Odd Tree

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.

Example 1:

Input: root = {5,4,2,3,3,7}
Output: false

Approach

Java

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class EvenOddTree {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(3);
        root.right.left = new TreeNode(7);

        System.out.println(isEvenOddTree(root));
    }

    static boolean isEvenOddTree(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        if (root == null)
            return true;
        q.add(root);
        boolean flag = true;
        while (!q.isEmpty()) {
            int len = q.size();
            List<Integer> v = new ArrayList<Integer>();
            while (len > 0 && flag == true) {
                root = q.poll();
                if ((root.val) % 2 == 0)
                    return false;
                v.add(root.val);
                if (root.left != null)
                    q.add(root.left);
                if (root.right != null)
                    q.add(root.right);
                len--;
            }
            if (flag == true) {
                for (int i = 0; i < v.size() - 1; i++) {
                    if (v.get(i) >= v.get(i + 1))
                        return false;
                }
            }
            while (len > 0 && flag == false) {
                root = q.poll();
                if (root.val % 2 == 1)
                    return false;
                v.add(root.val);
                if (root.left != null)
                    q.add(root.left);
                if (root.right != null)
                    q.add(root.right);
                len--;
            }
            if (flag == false) {
                for (int i = 0; i < v.size() - 1; i++) {
                    if (v.get(i) <= v.get(i + 1))
                        return false;
                }
            }
            flag = !flag;
        }
        return true;
    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
//struct for treenode
struct TreeNode{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data=data;
        this->left=NULL;
        this->right=NULL;
    }
}; 

bool isEvenOddTree(TreeNode* root) 
{
        queue<TreeNode*>q;
        if(root==NULL)
               return true;
        q.push(root);
        bool flag=true;
        while(!q.empty())
        {
            int len=q.size();
            vector<int> v;
            while(len>0&&flag==true)
            {
                root=q.front();
                if((root->data)%2==0)
                    return false;
                v.push_back(root->data);
                q.pop();
                if(root->left)
                      q.push(root->left);
                if(root->right)
                       q.push(root->right);
                len--;
            }
            if(flag==true)
            {
            for(int i=0;i<v.size()-1;i++)
              {
                 if(v[i]>=v[i+1])
                       return false;
              }
            }
            while(len>0&&flag==false)
            {
                root=q.front();
                if((root->data)&1)
                    return false;
                v.push_back(root->data);
                q.pop();
                if(root->left)
                      q.push(root->left);
                if(root->right)
                       q.push(root->right);
                 len--;
            }
            if(flag==false)
            {
             for(int i=0;i<v.size()-1;i++)
              {
                 if(v[i]<=v[i+1])
                       return false;
              }
            }
            flag=!flag;
        }
        return true;
}

int main()
{
   TreeNode *root=new TreeNode(5);
   root->left=new TreeNode(4);
   root->right=new TreeNode(2);
   root->left->left=new TreeNode(3);
   root->left->right=new TreeNode(3);
   root->right->left=new TreeNode(7);
 
   if(isEvenOddTree(root))
     cout<<"true";
   else
     cout<<"false";
    
  return 0;
   
}