Even Odd Tree

Even Odd Tree

What is this problem about?

The Even Odd Tree interview question asks you to verify if a binary tree satisfies specific "Even-Odd" conditions based on its levels.

• For even-indexed levels (0, 2, 4...): All nodes must have odd integer values, and values must be in strictly increasing order from left to right.
• For odd-indexed levels (1, 3, 5...): All nodes must have even integer values, and values must be in strictly decreasing order from left to right. If any node violates these rules, the tree is not an Even-Odd tree.

Why is this asked in interviews?

Microsoft and Meta ask this Tree interview pattern to test your proficiency with Breadth-First Search (BFS). Level-order traversal is the most natural way to process a tree level-by-level and verify properties that depend on node neighbors within the same level. It checks your ability to manage state (like the previous node's value) while moving through a queue.

Algorithmic pattern used

This problem is solved using Level-Order Traversal (BFS).

1. Use a Queue to process nodes level by level.
2. For each level, track the prev_value.
3. For each node in the level:
   • Check the parity (even/odd) based on the level index.
   • Compare the current value with prev_value to ensure the strictly increasing or decreasing order.
   • Add children to the queue for the next level.
4. If all nodes pass, return True.

Example explanation

Level 0 (Root): Value 5 (Odd). prev = 5. Level is even index, OK. Level 1: Children are 4 and 2.

• 4 is even, OK.
• 2 is even, OK.
• 4 > 2, so level is strictly decreasing. OK. Level 2: Children of 4 and 2 are 3, 5, 7.
• All are odd, OK.
• 3 < 5 < 7, so level is strictly increasing. OK. This tree is an Even-Odd tree.

Common mistakes candidates make

• Strict Ordering: Forgetting that the order must be strictly increasing/decreasing (i.e., 5, 5 is invalid).
• Parity Swap: Confusing the rules (Even level -> Odd values, Odd level -> Even values).
• Initialization: Not resetting the prev_value correctly for each new level.

Interview preparation tip

Practice using queue.size() within a loop to process nodes level-by-level in BFS. This is a very clean way to know exactly when one level ends and another begins without needing complex markers.