#1609

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Even Odd Tree

Determine if a binary tree meets Even-Odd rules by checking value parity and strict ordering at each level efficiently.

Problem Statement

Given the root of a binary tree, determine whether the tree is an Even-Odd tree. A tree is considered Even-Odd if nodes at even-indexed levels contain strictly increasing odd values and nodes at odd-indexed levels contain strictly decreasing even values.

Each level must maintain the correct parity and ordering: level 0 values are odd and increasing, level 1 values are even and decreasing, level 2 odd and increasing, and so on. Return true if the tree meets these conditions, otherwise return false.

Examples

Example 1

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

Output: true

The node values on each level are: Level 0: [1] Level 1: [10,4] Level 2: [3,7,9] Level 3: [12,8,6,2] Since levels 0 and 2 are all odd and increasing and levels 1 and 3 are all even and decreasing, the tree is Even-Odd.

Example 2

Input: root = [5,4,2,3,3,7]

Output: false

The node values on each level are: Level 0: [5] Level 1: [4,2] Level 2: [3,3,7] Node values in level 2 must be in strictly increasing order, so the tree is not Even-Odd.

Example 3

Input: root = [5,9,1,3,5,7]

Output: false

Node values in the level 1 should be even integers.

Constraints

The number of nodes in the tree is in the range [1, 105].
1 <= Node.val <= 106

Solution Approach

Use Breadth-First Search

Perform a BFS traversal to visit nodes level by level. Track each level separately to ensure proper parity and ordering constraints. This aligns with the primary pattern of binary-tree traversal and state tracking.

Validate Level Parity and Ordering

For each level, check that all nodes have the correct odd/even values and that they follow strictly increasing or decreasing order based on the level index. Immediately return false if any node violates the rules.

Handle Edge Cases Efficiently

Consider single-node trees, null children, or levels with one node. BFS ensures no level is skipped and avoids miscounting positions, which are common failure modes in Even-Odd Tree validation.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

Time complexity is O(n) since each node is visited exactly once. Space complexity is O(n) due to storing nodes in a queue for BFS traversal at each level.

What Interviewers Usually Probe

Check that nodes on the same level follow strict ordering based on level parity.
Ask about handling empty children and single-node levels without skipping checks.
Expect awareness of BFS for layer-by-layer state tracking rather than DFS.

Common Pitfalls or Variants

Common pitfalls

Failing to enforce strictly increasing or decreasing order per level.
Misclassifying node parity by level index instead of node values.
Skipping null children and causing incorrect level sequences.

Follow-up variants

Check for Even-Odd properties in an N-ary tree using the same BFS pattern.
Return the first level that violates Even-Odd rules instead of a boolean.
Modify the problem to allow non-strict ordering and validate accordingly.

FAQ

What defines an Even-Odd Tree in LeetCode problem 1609?

An Even-Odd Tree has levels where even-indexed levels contain strictly increasing odd values and odd-indexed levels contain strictly decreasing even values.

Can BFS be replaced with DFS for checking Even-Odd Tree?

DFS is possible, but BFS simplifies level tracking and state validation, reducing the risk of misclassifying node levels.

What are common mistakes when implementing Even-Odd Tree checks?

Mistakes include ignoring the parity of node values, failing to enforce strict ordering, or skipping null nodes in level processing.

What constraints should I consider for node values?

Node values range from 1 to 10^6, and the number of nodes is between 1 and 10^5, requiring O(n) traversal for efficiency.

How does the primary pattern of Binary-tree traversal and state tracking apply?

It ensures each level is validated individually for parity and order, which directly aligns with the Even-Odd Tree conditions.

terminal

Solution

Solution 1: BFS

BFS traverses level by level. Each level is judged by its parity. The node values at each level are either all even or all odd, and they are strictly increasing or decreasing.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
        even = 1
        q = deque([root])
        while q:
            prev = 0 if even else inf
            for _ in range(len(q)):
                root = q.popleft()
                if even and (root.val % 2 == 0 or prev >= root.val):
                    return False
                if not even and (root.val % 2 == 1 or prev <= root.val):
                    return False
                prev = root.val
                if root.left:
                    q.append(root.left)
                if root.right:
                    q.append(root.right)
            even ^= 1
        return True

Solution 2: DFS

DFS performs a pre-order traversal of the binary tree, and similarly judges whether it meets the conditions based on the parity of the layer where the node is located. During the traversal, a hash table is used to record the node value that was most recently visited at each layer.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
        even = 1
        q = deque([root])
        while q:
            prev = 0 if even else inf
            for _ in range(len(q)):
                root = q.popleft()
                if even and (root.val % 2 == 0 or prev >= root.val):
                    return False
                if not even and (root.val % 2 == 1 or prev <= root.val):
                    return False
                prev = root.val
                if root.left:
                    q.append(root.left)
                if root.right:
                    q.append(root.right)
            even ^= 1
        return True

Continue Practicing

#1457 pseudo palindromic paths in a binary tree #1448 count good nodes in binary tree #1379 find a corresponding node of a binary tree in a clone of that tree