Even Odd Tree

A binary tree is named Even-Odd if it meets the following conditions:

• The root of the binary tree is at level index 0, its children are at level index 1, their children are at level index 2, etc.
• For every even-indexed level, all nodes at the level have odd integer values in strictly increasing order (from left to right).
• For every odd-indexed level, all nodes at the level have even integer values in strictly decreasing order (from left to right).

Given the root of a binary tree, return true if the binary tree is Even-Odd, otherwise return false.

For example, consider the following binary tree:

    1
   / \
  10  4
 /  \ / \
3   X 7  9

In this example, if X = null, the tree is Even-Odd because:

• Level 0: [1] (odd)
• Level 1: [10, 4] (even and decreasing)
• Level 2: [3, 7, 9] (odd and increasing)

However, if we change the tree slightly to:

    5
   / \
  4   2
 / \ / X
3   3 7

This tree is not Even-Odd because level 2 ([3, 3, 7]) is not strictly increasing.

Write a function to determine if a given binary tree is Even-Odd.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

from collections import deque

class Solution:
    def isEvenOddTree(self, root: TreeNode) -> bool:
        if not root:
            return True

        queue = deque([root])
        level = 0

        while queue:
            level_size = len(queue)
            prev_val = None

            for _ in range(level_size):
                node = queue.popleft()

                if level % 2 == 0:  # Even level
                    if node.val % 2 == 0:
                        return False
                    if prev_val is not None and node.val <= prev_val:
                        return False
                else:  # Odd level
                    if node.val % 2 != 0:
                        return False
                    if prev_val is not None and node.val >= prev_val:
                        return False

                prev_val = node.val

                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            level += 1

        return True

Naive Solution

The naive approach would involve traversing the tree and checking each level individually to ensure it satisfies the even-odd properties. This can be done using a Breadth-First Search (BFS). For each level, we'd need to store the node values and then iterate through them to check if they are odd/even and strictly increasing/decreasing, as required.

Optimal Solution

The provided solution is already optimized as it traverses the tree only once using BFS and performs the necessary checks on each node as it's visited. This avoids unnecessary storage or re-computation. The time complexity is O(N), where N is the number of nodes in the tree, as each node is visited once.

Big(O) Run-time Analysis

The run-time complexity is O(N), where N is the number of nodes in the binary tree. This is because the algorithm uses Breadth-First Search (BFS) to visit each node exactly once. The operations performed at each node (checking its value and comparing it with the previous node) take constant time, O(1). Therefore, the overall run-time is proportional to the number of nodes in the tree.

Big(O) Space Usage Analysis

The space complexity is O(W), where W is the maximum width of the binary tree. This is because the algorithm uses a queue to store the nodes at each level during the BFS traversal. In the worst-case scenario, the queue can contain all nodes at the widest level of the tree. For a complete binary tree, the maximum width is approximately N/2, where N is the number of nodes in the tree. Therefore, the space complexity can be considered O(N) in the worst case. However, it's more accurate to describe it as O(W), where W is the maximum width of the tree.

Edge Cases

1. Empty Tree:
   • If the root is None, the tree is considered Even-Odd, and the function should return True.
2. Single Node Tree:
   • If the tree contains only the root node, it should be checked if the root value is odd. If it is, the tree is Even-Odd; otherwise, it is not.
3. Tree with One Level:
   • For a tree where all nodes are at level 0, all node values must be odd and in strictly increasing order (if there's more than one node). This case is naturally handled by the main logic.
4. Non-integer Values:
   • The code assumes that all node values are integers. If non-integer values are present, the modulo operation (%) may not behave as expected. Handling non-integer values would require additional checks or type conversions.
5. Large Tree:
   • For very large trees, the queue in the BFS traversal may consume a significant amount of memory. However, this is inherent to the BFS approach, and the space complexity is O(W), where W is the maximum width of the tree.
6. Duplicate Values in Even Levels:
   • The check for strictly increasing order on even levels and strictly decreasing order on odd levels will fail if there are duplicate values. For example, [1, 3, 3] on an even level would cause the function to return False.
7. Invalid Input Types:
   • If the input root is not a TreeNode object, the code may raise an exception. Handling this case would require an explicit type check.