LeetCode 1609: Even Odd Tree

Explanation

To determine if a binary tree is Even-Odd, we need to traverse the tree level by level and check if the values at each level satisfy the given conditions. If any level violates the conditions, then the tree is not Even-Odd. We can perform a BFS traversal of the tree while keeping track of the level and the values at each level.

Algorithm:

1. Perform a BFS traversal of the binary tree.
2. Keep track of the level (even or odd) and the expected value order for that level.
3. At each level, check if the values satisfy the conditions:
   • For even levels, values should be odd and strictly increasing.
   • For odd levels, values should be even and strictly decreasing.
4. If any level violates the conditions, return false.
5. If all levels satisfy the conditions, return true.

Time Complexity:

The time complexity of this algorithm is O(n), where n is the number of nodes in the binary tree. This is because we visit each node exactly once during the BFS traversal.

Space Complexity:

The space complexity of this algorithm is O(n), where n is the number of nodes in the binary tree. This is due to the space used by the queue for BFS traversal.

class Solution {
    public boolean isEvenOddTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int level = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            int prevValue = level % 2 == 0 ? Integer.MIN_VALUE : Integer.MAX_VALUE;

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();

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

                prevValue = node.val;

                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            level++;
        }

        return true;
    }
}