How do you solve Even Odd Tree?

Use BFS with a queue initialized with the root node. Track the current level index. For each level, dequeue all nodes, record their values, and enqueue their children. Then validate the level's values for parity and strict ordering according to the level's parity (even or odd). If any validation fails, return false immediately. If all levels pass, return true after traversal completes.

What pattern does Even Odd Tree use?

The Pattern: BFS (Level-Order Traversal with Conditional Validation) The Heuristic: When a problem requires checking properties that depend on node levels in a tree, use BFS to process nodes level by level, enabling isolated validation of each level's constraints before proceeding.

Even Odd Tree — BFS

Q: What is the time complexity of Even Odd Tree?

O(n). Each node is enqueued and dequeued exactly once during BFS, and each level's validation iterates over all nodes at that level once, resulting in a total linear time complexity proportional to the number of nodes.

Problem

Given the root of a binary tree, return true if the binary tree is an Even-Odd Tree, where the nodes on even-indexed levels are strictly increasing and odd-valued, and the nodes on odd-indexed levels are strictly decreasing and even-valued; otherwise, return false.

The number of nodes in the tree is in the range [1, 10⁵]
1 ≤ Node.val ≤ 10⁶

Example

Input: root = [1,10,4,3,null,7,9,12,8,6,null,null,2]

Output: true

Level 0: [1] is odd and strictly increasing trivially. Level 1: [10, 4] are even and strictly decreasing (10 > 4). Level 2: [3, 7, 9] are odd and strictly increasing (3 < 7 < 9). Level 3: [12, 8, 6, 2] are even and strictly decreasing (12 > 8 > 6 > 2). All levels satisfy the conditions, so the tree is an Even-Odd Tree.

Approach

Straightforward Solution

A naive approach might attempt to traverse the tree multiple times or use depth-first search with complex state tracking, which complicates level-based validation and risks inefficiency.

Core Observation

The problem requires checking level-by-level properties of the tree nodes, specifically parity and strict ordering, which naturally suggests a breadth-first search (BFS) traversal to process nodes level-wise.

Path to Optimal

Preview

Recognizing that BFS inherently processes nodes level by level, the solution uses a queue to perform a level-order traversal. At each level, it collects node values and validates the parity and strict ordering constraints in a single pass…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use BFS with a queue initialized with the root node. Track the current level index…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each node is enqueued and dequeued exactly once during BFS, and each level's validation iterates over all nodes at that level once, resulting in a total linear time complexity proportional to the number of nodes.

Space

O(w)

The auxiliary space is dominated by the queue storing nodes at the widest level of the tree, which can be up to O(n) in the worst case for a balanced tree; the values list per level also scales with the level width.

Solution

Python

1from collections import deque
2
3class Solution:
  def isEvenOddTree(self, root: TreeNode) -> bool:
      if not root:
          return True 
      
      queue = deque([root])
      level = 0 
      
      while queue:
          size = len(queue)
          values = [] 
          
          for _ in range(size):
              node = queue.popleft() 
              values.append(node.val) 
              
              if node.left:
                  queue.append(node.left) 
              if node.right:
                  queue.append(node.right) 
          
          if level % 2 == 0:
              for i in range(len(values)):
                  if values[i] % 2 == 0 or (i > 0 and values[i] <= values[i - 1]):
                      return False 
          else:
              for i in range(len(values)):
                  if values[i] % 2 != 0 or (i > 0 and values[i] >= values[i - 1]):
                      return False 
          level += 1 
      
      return True 

Step-by-Step Solution

1

Return True Immediately for Empty Tree

5if not root:
6    return True 

Objective

To handle the edge case where the input tree is empty by returning True, as an empty tree trivially satisfies the Even-Odd Tree conditions.

Key Insight

An empty tree has no nodes violating the conditions, so it is vacuously an Even-Odd Tree. Early return avoids unnecessary processing and simplifies the main logic.

Interview Quick-Check

State & Boundaries

Check if the root is None and return True immediately to handle the empty input edge case.

2

Perform BFS to Traverse Tree Level by Level

To traverse the tree in level order using a queue, collecting node values at each level for validation.

3

Validate Level Values for Parity and Strict Ordering

To check that node values at each level satisfy the Even-Odd Tree conditions: odd values strictly increasing on even levels, even values strictly decreasing on odd levels.

4

Return True After Successful Validation of All Levels

To return True after all levels have been processed and validated without violations.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 26 Critical

if values[i] % 2 == 0 or (i > 0 and values[i] <= values[i - 1]):

Check if the value is even or not strictly increasing compared to the previous value.

This compound condition enforces the core Even-Odd Tree rule for even levels: all values must be odd and strictly increasing, which is essential for correctness.

Line 30 Critical

if values[i] % 2 != 0 or (i > 0 and values[i] >= values[i - 1]):

Check if the value is odd or not strictly decreasing compared to the previous value.

This condition enforces the Even-Odd Tree rule for odd levels: all values must be even and strictly decreasing, which is critical for correctness.

Full line-by-line criticality + rationale for all 24 lines available on Pro.

Test Your Understanding

Why is BFS the natural choice for validating level-specific constraints in a binary tree?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Even Odd Tree from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Even Odd Tree drill

or drill a free problem

1	`from collections import deque`
2
3	`class Solution:`
4	`def isEvenOddTree(self, root: TreeNode) -> bool:`
5	`if not root:`
6	`return True`
7
8	`queue = deque([root])`
9	`level = 0`
10
11	`while queue:`
12	`size = len(queue)`
13	`values = []`
14
15	`for _ in range(size):`
16	`node = queue.popleft()`
17	`values.append(node.val)`
18
19	`if node.left:`
20	`queue.append(node.left)`
21	`if node.right:`
22	`queue.append(node.right)`
23
24	`if level % 2 == 0:`
25	`for i in range(len(values)):`
26	`if values[i] % 2 == 0 or (i > 0 and values[i] <= values[i - 1]):`
27	`return False`
28	`else:`
29	`for i in range(len(values)):`
30	`if values[i] % 2 != 0 or (i > 0 and values[i] >= values[i - 1]):`
31	`return False`
32	`level += 1`
33
34	`return True`