⚡Flashcard Drill➔
NeetCode #461LC-1609MediumTrees
← Back to All Problems

#461 · #1609 · Even Odd Tree(奇偶树)

📌 Problem Statement & Constraints

A binary tree is even-odd if: every even-indexed level (the root is level 0) has strictly increasing values that are all odd, and every odd-indexed level has strictly decreasing values that are all even. Given the root, return whether it is even-odd. Constraints: the number of nodes is in [1, 10^5], 1 <= Node.val <= 10^6.

💡 Core Algorithmic Approaches

  1. Level-order traversal with a frozen level size, tracking the level index.
  2. On even levels: every value must be odd and strictly greater than the previous one.
  3. On odd levels: every value must be even and strictly less than the previous one.
  4. Checking the ordering on the fly avoids storing the whole level.

💻 Benchmark Python3 Implementation

class Solution:
    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
        from collections import deque
        q = deque([root])
        level = 0
        while q:
            n = len(q)
            prev = None
            for _ in range(n):
                node = q.popleft()
                if level % 2 == 0:         # even level: odd values, increasing
                    if node.val % 2 == 0 or (prev is not None and node.val <= prev):
                        return False
                else:                      # odd level: even values, decreasing
                    if node.val % 2 == 1 or (prev is not None and node.val >= prev):
                        return False
                prev = node.val
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            level += 1
        return True

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): every node is visited once.
💾 Space Complexity
O(w) for the widest level.

⚠️ Interview Pitfalls & Follow-ups

  • Swapping the parity rules: even levels need odd values increasing; odd levels need even values decreasing.
  • Using non-strict comparisons: both orderings are strict.
  • Forgetting the parity check on the values themselves: both conditions are required.
  • Resetting prev per node instead of per level: the ordering is within a level.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Trees Problems