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
- Level-order traversal with a frozen level size, tracking the level index.
- On even levels: every value must be odd and strictly greater than the previous one.
- On odd levels: every value must be even and strictly less than the previous one.
- 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
prevper 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.