Even Odd Tree

Problem Statement

In the context of binary trees, an Even-Odd tree is defined by its unique structuring based on levels and the values of nodes in these levels. Specifically, the structure is layered by indices starting from root at index 0, moving to its children at index 1, and so forth. The conditions that segregate this as an Even-Odd tree include:

• Every node in even-indexed levels (e.g., 0, 2, 4,...) must store odd values that strictly increase from left to right.
• Conversely, every node in odd-indexed levels (e.g., 1, 3, 5,...) must hold even values that strictly decrease from left to right.

The challenge lies in validating whether a given binary tree, based on its root node, adheres to these properties, returning true if it does, and false otherwise.

Examples

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.

Constraints

• The number of nodes in the tree is in the range [1, 105].
• 1 <= Node.val <= 106

Approach and Intuition

To determine if a given binary tree qualifies as an Even-Odd tree, we need to employ a level-by-level traversal mechanism, such as Breadth-First Search (BFS). This approach allows us to:

1. Visit each node level-wise while tracking the level's index to apply the appropriate even or odd rules.
2. For even-indexed levels, verify that all the node values are odd and that these values are in a strictly increasing order.
3. For odd-indexed levels, ensure all values are even and arranged in a strictly decreasing sequence.

Step-by-step breakdown:

1. Initiate a BFS traversal:
   • Typically, use a queue where each element consists of the node and its level.
   • Begin with the root node at level 0.
2. Process nodes level by level:
   • Keep track of the previous value to compare the current node’s value based on the level.
   • Depending on if the level is even or odd, check:
     • Even level: Nodes should have odd values, and each next node should have a value greater than the previous.
     • Odd level: Nodes should have even values, with each subsequent node having a smaller value than the previous.
3. Include conditions to immediately return false if any rule is violated at any level.

Here's what makes this problem interesting and challenging:

• Ensuring that the values are not only odd or even as appropriate but also checking the strictly increasing or decreasing condition.
• Edge cases such as trees with minimum nodes or values can test the boundary conditions of the aforementioned rules.

Solutions

class Solution {
public:
    bool checkEvenOddTree(TreeNode* root) {
        queue<TreeNode*> nodesQueue;
        TreeNode* currNode = root;
        nodesQueue.push(currNode);
    
        bool isEvenLevel = true;
    
        while (!nodesQueue.empty()) {
            int levelSize = nodesQueue.size();
            int lastValue = isEvenLevel ? INT_MIN : INT_MAX;
    
            while (levelSize > 0) {
                currNode = nodesQueue.front();
                nodesQueue.pop();
    
                if ((isEvenLevel && (currNode->val % 2 == 0 || currNode->val <= lastValue)) || 
                    (!isEvenLevel && (currNode->val % 2 != 0 || currNode->val >= lastValue))) {
                    return false;
                }
                lastValue = currNode->val;
                if (currNode->left) {
                    nodesQueue.push(currNode->left);
                }
                if (currNode->right) {
                    nodesQueue.push(currNode->right);
                }
                levelSize--;
            }
            isEvenLevel = !isEvenLevel;
        }
        return true;
    }
};