Even Odd Tree

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;
    }
};

The provided C++ solution defines a method to determine if a binary tree meets specific criteria for an "Even Odd Tree." In an "Even Odd Tree," nodes at even-indexed levels all contain odd integer values that strictly increase from left to right, whereas nodes at odd-indexed levels contain even integer values that strictly decrease from left to right.

Here’s a breakdown of how the solution works:

1. The method checkEvenOddTree takes the root node of a tree as its argument.
2. A queue, nodesQueue, is initialized for a level-order traversal, starting with the root node.
3. A boolean, isEvenLevel, tracks the current level's parity (starting with true for the root level being even).
4. The tree is traversed level by level using a while loop, continuing as long as there are nodes in the queue.
5. Within the loop:
   • levelSize stores the number of nodes at the current level.
   • lastValue initializes to INT_MIN for even levels and INT_MAX for odd levels to help in comparison of node values within a level.
   • A nested while loop iterates through each node at the current level:
     • The value of the current node is checked against the parity requirement (odd values for even levels and even values for odd levels) and whether it maintains the increasing/decreasing order when compared to lastValue.
     • If the node violates either condition, the method immediately returns false.
     • lastValue is then updated to the current node's value.
     • The node's children are added to the queue.
     • levelSize is decremented.
6. After processing all nodes at a level, isEvenLevel is toggled to switch to the next level's parity.
7. If all levels are processed successfully without returning false, the method returns true, confirming the tree is an "Even Odd Tree."

This approach ensures the tree is checked efficiently, with each node processed once in a level-order manner, allowing for both value and order conditions to be verified at each level.

public class Solution {
    public boolean checkEvenOddTree(TreeNode root) {
        Queue<TreeNode> nodesQueue = new LinkedList<>();
        TreeNode node = root;
        nodesQueue.add(node);
        boolean isEvenLevel = true;

        while (!nodesQueue.isEmpty()) {
            int levelSize = nodesQueue.size();
            int prevValue = isEvenLevel ? Integer.MIN_VALUE : Integer.MAX_VALUE;

            while (levelSize > 0) {
                node = nodesQueue.poll();

                if ((isEvenLevel && (node.val % 2 == 0 || node.val <= prevValue)) ||
                        (!isEvenLevel && (node.val % 2 == 1 || node.val >= prevValue))) {
                    return false;
                }

                prevValue = node.val;
                if (node.left != null) {
                    nodesQueue.add(node.left);
                }
                if (node.right != null) {
                    nodesQueue.add(node.right);
                }
                levelSize--;
            }
            isEvenLevel = !isEvenLevel;
        }
        return true;
    }
}

In the provided Java solution for checking if a binary tree is an "Even Odd Tree," the code follows a specific set of rules to determine tree validity based on level order traversal properties:

1. Tree Node Definition and Initialization:

   • A custom TreeNode class is likely defined elsewhere, which includes integers for both the value (val) and pointers to left and right child (left, right).
   • The root of the tree is taken as an input for the method checkEvenOddTree.

2. Queue for Level Order Traversal:

   • A Queue<TreeNode> is utilized to facilitate level order traversal of the tree, starting with the root node.

3. Level-by-level Traversal and Validation:

   • The main loop runs as long as there are nodes in the queue.
   • Inside the loop, it determines the number of nodes (levelSize) at the current level to process each level entirely before moving to the next.
   • A previous value prevValue is set based on whether the current level is even or odd:
     • For even levels, it starts at the smallest possible value (Integer.MIN_VALUE).
     • For odd levels, it starts at the largest possible value (Integer.MAX_VALUE).
   • Each node at the current level is inspected to ensure it meets the criteria for even or odd levels:
     • On even levels, node values must be odd and strictly increasing.
     • On odd levels, node values must be even and strictly decreasing.
   • If any node violates these conditions, the method returns false immediately.

4. Child Node Processing:

   • Child nodes (left and right) of the current node are added to the queue to be processed in the subsequent iterations.

5. Level Switching:

   • After processing all nodes at the current level, the level is switched from even to odd or vice versa for the next iteration.

6. Result:

   • If the loop concludes without finding any discrepancies, it returns true, indicating that the tree satisfies the 'Even Odd Tree' condition.

This method efficiently traverses through the tree, ensuring that at every level, nodes adhere to the defined alternation between even and odd levels, providing a robust solution to determine the validity of the tree structure as per the stated rules.

class Solution:
    def checkEvenOddTree(self, root_node: Optional[TreeNode]) -> bool:
        node_queue = deque()
        node = root_node
        node_queue.append(node)

        is_even_level = True

        while node_queue:
            level_size = len(node_queue)

            previous_node_value = float("-inf") if is_even_level else float("inf")

            while level_size > 0:
                node = node_queue.popleft()

                if (is_even_level and (node.val % 2 != 1 or node.val <= previous_node_value)) or \
                   (not is_even_level and (node.val % 2 != 0 or node.val >= previous_node_value)):
                    return False

                previous_node_value = node.val
                if node.left:
                    node_queue.append(node.left)
                if node.right:
                    node_queue.append(node.right)

                level_size -= 1

            is_even_level = not is_even_level

        return True

In the provided Python solution, the task is to verify if a binary tree is an "Even Odd Tree." To clarify, an "Even Odd Tree" has nodes at even-numbered levels with increasing odd values, and nodes at odd-numbered levels with strictly decreasing even values.

Here’s how the Python code achieves this validation:

1. Utilize a queue (node_queue) to employ a level order traversal of the tree, starting with the root node.
2. Use a flag (is_even_level) that toggles between True and False to track the current tree level's nature (even or odd levels).
3. Iterate through each level in the tree:
   • Initialize previous_node_value to negative infinity (float("-inf")) if it is an even level implying checking for increasing order, or positive infinity (float("inf")) if it is an odd level implying decreasing order.
   • For each node in the current level:
     • Check if the conditions (odd values increasing at even levels and even values decreasing at odd levels) hold. If not, immediately return False.
     • Update previous_node_value to current node value for comparison with the next node in the level.
     • Append the left and right child nodes to the queue for further level checks.
4. After processing all nodes at the current level, invert is_even_level to adjust for the next level.
5. If all conditions hold across all levels, return True indicating the tree meets the even-odd criterion.

By executing the solution on the tree with level-traversal and conditional validation, it efficiently ensures that the structure fulfills the conditions of an "Even Odd Tree" with a time complexity primarily dependent on the number of nodes in the tree.