Even Odd Tree

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.

Q: 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.

Medium BFS

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

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. This approach cleanly separates levels and allows immediate failure detection, ensuring O(n) time complexity.

Optimal Approach

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.

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.

Pattern Spotlight

BFS (Level-Order Traversal with Conditional Validation)

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.

Solution

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

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.

Perform BFS to Traverse Tree Level by Level

8queue = deque([root])
9level = 0 
11while 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) 

Objective

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

Key Insight

BFS naturally groups nodes by their depth, enabling the algorithm to process one level at a time. By dequeuing all nodes at the current level and enqueuing their children, the algorithm maintains a clear boundary between levels, which is essential for applying level-specific parity and ordering rules.

Interview Quick-Check

Core Logic

Use a queue to process nodes level by level, collecting their values and enqueuing their children for the next level.

State & Boundaries

Use a loop that iterates exactly 'size' times per level to ensure only nodes at the current level are processed.

Complexity

Each node is processed once, ensuring O(n) time complexity.

Validate Level Values for Parity and Strict Ordering

24if 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 
28else:
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 
32level += 1 

Objective

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.

Key Insight

The level index determines the parity and ordering constraints. For even levels, values must be odd and strictly increasing; for odd levels, values must be even and strictly decreasing. Iterating through the collected values with these checks ensures correctness. Immediate return on failure avoids unnecessary work.

Interview Quick-Check

Core Logic

Validate that values at even levels are odd and strictly increasing, and values at odd levels are even and strictly decreasing.

Common Pitfalls & Bugs

Ensure to check both parity and ordering conditions; missing either leads to incorrect acceptance.

State & Boundaries

Use index-based comparisons to enforce strict ordering, starting from the second element.

Return True After Successful Validation of All Levels

34	`return True`

Objective

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

Key Insight

If the BFS completes without returning False, it means all levels satisfy the Even-Odd Tree conditions. Returning True confirms the tree meets the problem requirements.

Interview Quick-Check

Core Logic

Return True only after confirming all levels meet the parity and ordering constraints.

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.

Line 8 Core

queue = deque([root])

Initialize the BFS queue with the root node.

Starting BFS with the root node sets up the level-order traversal, enabling processing of nodes level by level.

Line 16 Core

node = queue.popleft()

Dequeue the next node from the queue.

Dequeuing nodes in FIFO order preserves BFS traversal order, essential for level-by-level processing.

Line 19 Core

if node.left:

If the current node has a left child, enqueue it.

Adding children to the queue prepares the next level for processing, maintaining BFS traversal.

Line 21 Core

if node.right:

If the current node has a right child, enqueue it.

Adding the right child to the queue ensures all nodes at the next level are processed.

Line 27 Core

return False

Return False if the even level validation fails.

Immediate failure return prevents unnecessary further processing once a violation is detected.

Line 31 Core

return False

Return False if the odd level validation fails.

Returning immediately on failure avoids unnecessary computation and signals the tree does not meet the criteria.

Line 34 Core

return True

Return True after all levels have been validated successfully.

If no violations are found during BFS traversal, the tree satisfies the Even-Odd Tree conditions, so returning True is correct.

Line 5 Core

if not root:

Check if the root is None (empty tree).

An empty tree trivially satisfies the Even-Odd Tree conditions, so returning True immediately avoids unnecessary processing.

Line 6 Core

return True

Return True for empty tree.

This early return handles the edge case cleanly and prevents errors in subsequent BFS logic.

Line 9 Core

level = 0

Initialize the level counter to zero.

Tracking the current level index is essential for applying the correct parity and ordering rules at each level.

Line 12 Core

size = len(queue)

Record the number of nodes at the current level.

Knowing the level size allows processing exactly one level's nodes per iteration, preserving level boundaries.

Line 13 Core

values = []

Initialize a list to store values of nodes at the current level.

Collecting values enables validation of parity and ordering constraints after processing the entire level.

Line 17 Core

values.append(node.val)

Append the current node's value to the level values list.

Storing node values allows later validation of the level's parity and ordering constraints.

Line 20 Core

queue.append(node.left)

Enqueue the left child node.

This step ensures the left child will be processed in the next BFS iteration, preserving level order.

Line 22 Core

queue.append(node.right)

Enqueue the right child node.

This maintains the BFS invariant of processing nodes level by level.

Line 24 Core

if level % 2 == 0:

Check if the current level is even-indexed.

Determining level parity is necessary to apply the correct validation rules for node values.

Line 25 Core

for i in range(len(values)):

Iterate over all values at the current even level.

Checking each value ensures the entire level satisfies the parity and ordering constraints.

Line 28 Core

else:

Handle the odd-indexed level case.

Odd levels have different parity and ordering constraints, so separate validation logic is required.

Line 29 Core

for i in range(len(values)):

Iterate over all values at the current odd level.

Each value must be checked to ensure the level satisfies the odd-level constraints.

Line 32 Core

level += 1

Increment the level counter after processing the current level.

Advancing the level index ensures the correct parity rules are applied to the next level.

Line 11 Standard

while queue:

Continue BFS while there are nodes to process.

The loop ensures all nodes in the tree are visited level by level until the queue is empty.

Line 15 Standard

for _ in range(size):

Iterate over all nodes at the current level.

Processing exactly 'size' nodes ensures the BFS processes one level at a time, maintaining level integrity.

Test Your Understanding

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

Because BFS processes nodes level by level, it cleanly separates nodes by their depth, allowing direct and isolated validation of each level's properties without complex state management or repeated traversals.

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`

8	`queue = deque([root])`
9	`level = 0`
11	`while queue:`
12	`size = len(queue)`
13	`values = []`
15	`for _ in range(size):`
16	`node = queue.popleft()`
17	`values.append(node.val)`
19	`if node.left:`
20	`queue.append(node.left)`
21	`if node.right:`
22	`queue.append(node.right)`

Problem

Example

Approach

Solution

Step-by-Step Solution

Return True Immediately for Empty Tree

Perform BFS to Traverse Tree Level by Level

Validate Level Values for Parity and Strict Ordering

Return True After Successful Validation of All Levels

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.