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) {
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        if (root == null || root.val %2 == 0) {
            return false;
        }
        queue.add(root);
        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){
                    queue.add(temp.left);
                }

                if (temp.right != null) {
                    queue.add(temp.right);
                }
            }
            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.