1609. Even Odd Tree - Explanation

1. Breadth First Search

Intuition

An Even-Odd tree has specific constraints on each level: even-indexed levels must have strictly increasing odd values, while odd-indexed levels must have strictly decreasing even values. BFS naturally processes the tree level by level, making it ideal for checking these per-level conditions.

As we process each level, we track whether it is even or odd and verify that every node satisfies both the parity constraint (odd values on even levels, even values on odd levels) and the ordering constraint (increasing or decreasing based on level).

Algorithm

Initialize a queue with the root and a boolean even = true to track the current level type.
For each level:
- Set prev to negative infinity (for even levels) or positive infinity (for odd levels).
- Process all nodes at this level:
  - Check if the node's value has the correct parity for the level.
  - Check if the value maintains the required ordering relative to prev.
  - If either check fails, return false.
  - Add the node's children to the queue and update prev.
- Toggle the even flag for the next level.
If all levels pass, return true.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
        even = True
        q = deque([root])

        while q:
            prev = float("-inf") if even else float("inf")
            for _ in range(len(q)):
                node = q.popleft()

                if even and (node.val % 2 == 0 or node.val <= prev):
                    return False
                elif not even and (node.val % 2 == 1 or node.val >= prev):
                    return False

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

                prev = node.val

            even = not even

        return True

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

2. Depth First Search

Intuition

DFS can also solve this problem by tracking the last seen value at each level. As we traverse the tree in preorder (left to right), the first time we visit a level establishes the starting value. Subsequent visits to that level must satisfy the ordering constraint relative to the previous value we recorded.

We maintain an array where levels[i] stores the most recently seen value at level i. This lets us check ordering across a level even though DFS does not process levels sequentially.

Algorithm

Create a levels array to track the last value seen at each depth.
Define a recursive DFS function that takes a node and its level:
- If the node is null, return true.
- Check if the node's value has the correct parity for the level. Return false if not.
- If this is the first node at this level, record its value.
- Otherwise, check the ordering constraint against levels[level]. Return false if violated, then update levels[level].
- Recursively check the left and right children at level + 1.
Return the result of calling DFS on the root at level 0.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
        levels = []

        def dfs(node, level):
            if not node:
                return True

            even = level % 2 == 0
            if ((even and node.val % 2 == 0) or
                (not even and (node.val % 2 == 1))
            ):
                return False

            if len(levels) == level:
                levels.append(node.val)
            else:
                if ((even and node.val <= levels[level]) or
                    (not even and node.val >= levels[level])
                ):
                    return False
                levels[level] = node.val

            return dfs(node.left, level + 1) and dfs(node.right, level + 1)

        return dfs(root, 0)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Iterative DFS

Intuition

This approach mimics recursive DFS using an explicit stack, which can help avoid stack overflow for very deep trees. We store (node, level) pairs on the stack and process nodes in a similar order to recursive DFS.

The same levels array tracks the last seen value at each depth. By pushing the right child before the left child, we ensure left-to-right traversal order when popping.

Algorithm

Initialize a stack with (root, 0) and a levels array.
While the stack is not empty:
- Pop a (node, level) pair.
- Check the parity constraint for the node's value. Return false if violated.
- If this is the first node at this level, append the value to levels.
- Otherwise, check the ordering constraint and update levels[level]. Return false if violated.
- Push the right child (if exists) then the left child (if exists) with level + 1.
If processing completes without violations, return true.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
        stack = [(root, 0)]
        levels = []

        while stack:
            node, level = stack.pop()

            even = level % 2 == 0
            if ((even and node.val % 2 == 0) or
                (not even and node.val % 2 == 1)
            ):
                return False

            if len(levels) == level:
                levels.append(node.val)
            else:
                if ((even and node.val <= levels[level]) or
                    (not even and node.val >= levels[level])
                ):
                    return False
                levels[level] = node.val

            if node.right:
                stack.append((node.right, level + 1))
            if node.left:
                stack.append((node.left, level + 1))

        return True

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

Common Pitfalls

Confusing Level Index with Value Parity

Even-indexed levels (0, 2, 4, ...) must have odd VALUES, while odd-indexed levels (1, 3, 5, ...) must have even VALUES. It is easy to mix these up and check if values match the level parity, which is the opposite of what the problem requires. Remember: level parity and value parity must be different.

Using Non-Strict Inequality for Ordering

The problem requires STRICTLY increasing order on even levels and STRICTLY decreasing order on odd levels. Using <= instead of < for increasing, or >= instead of > for decreasing, will incorrectly accept trees where adjacent nodes have equal values. Equal values at the same level should cause the function to return false.

Forgetting to Reset Previous Value Between Levels

When processing each level, the prev tracking variable must be reset to an appropriate initial value (negative infinity for even levels, positive infinity for odd levels). If you forget to reset it or initialize it incorrectly, comparisons with the first node of each level will fail, causing valid trees to be rejected or invalid trees to be accepted.