# 1609. Even Odd Tree

Binary trees serve as a fundamental data structure in computer science, offering versatile solutions to various problems. One such intriguing problem is determining whether a given binary tree is an Even-Odd Tree. In this blog post, we’ll embark on a journey to understand the concept of an Even-Odd Tree and delve into an algorithmic solution to determine its nature using a breadth-first search (BFS) approach.

### Understanding the Problem:

An Even-Odd Tree is a binary tree where:

1. The root node has an odd value.
2. The values of nodes at even levels (1-indexed) are strictly decreasing from left to right.
3. The values of nodes at odd levels are strictly increasing from left to right.

Our task is to implement an algorithm to determine whether a given binary tree meets the criteria of an Even-Odd Tree.

### Approach and Code Explanation:

To solve this problem, we’ll use a breadth-first search (BFS) approach to traverse the binary tree level by level. During traversal, we’ll check if the current level meets the criteria of an Even-Odd Tree.

Here’s the breakdown of the Java solution:

``````class Solution {
public boolean isEvenOddTree(TreeNode root) {
if (root == null || root.val %2 == 0) {
return false;
}
int level = 1;

while(queue.size() > 0) {
int n = queue.size();
int prev = -1;
for(int i=0;i<n;i++) {
TreeNode temp = queue.poll();
if (level % 2 != 0) {
// Odd level
if (temp.left != null && temp.left.val % 2 != 0 ) {
return false;
}
if (temp.right != null && temp.right.val % 2 != 0 ) {
return false;
}

if (temp.left != null) {
if (prev != -1 && prev <= temp.left.val){
return false;
}
prev = temp.left.val;
}

if (temp.right != null) {
if (prev != -1 && prev <= temp.right.val){
return false;
}
prev = temp.right.val;
}

} else {
// Even level
if (temp.left != null && temp.left.val % 2 == 0 ) {
return false;
}
if (temp.right != null && temp.right.val % 2 == 0 ) {
return false;
}

if (temp.left != null) {
if (prev != -1 && prev >= temp.left.val){
return false;
}
prev = temp.left.val;
}

if (temp.right != null) {
if (prev != -1 && prev >= temp.right.val){
return false;
}
prev = temp.right.val;
}
}

if (temp.left != null){
}

if (temp.right != null) {
}
}
level++;
}
return true;
}
}``````

https://leetcode.com/problems/even-odd-tree/description/

1. We define a class `Solution` that contains the solution logic.
2. The `isEvenOddTree` method takes the root node of the binary tree as input and returns a boolean indicating whether the tree is an Even-Odd Tree.
3. We initialize a `LinkedList` named `queue` to perform breadth-first traversal of the binary tree. We start by adding the root node to the queue.
4. We check if the root node is null or has an even value. If so, we immediately return false.
5. We maintain a variable `level` to keep track of the current level during traversal.
6. Within the `while` loop, we process each level of the binary tree. At each level:
• We retrieve the current size of the queue (`n`) to process all nodes at the current level.
• We initialize a variable `prev` to keep track of the previous node’s value within the current level.
• We iterate through all nodes at the current level, removing them from the queue one by one (`temp = queue.poll()`).
• Depending on whether the level is odd or even, we perform specific checks:
• For odd levels: We ensure that the values are odd and strictly increasing from left to right.
• For even levels: We ensure that the values are even and strictly decreasing from left to right.
• We enqueue the left and right children of the current node if they exist.
7. Finally, we return true if the binary tree satisfies the conditions of an Even-Odd Tree.