LeetCode 1609 - Even Odd Tree

Here’s a fully detailed, reference-style solution guide for LeetCode 1609 - Even Odd Tree, following all your formatting

leetcodemediumtreebreadth-first-searchbinary-tree

LeetCode Problem 1609

Difficulty: 🟡 Medium
Topics: Tree, Breadth-First Search, Binary Tree

Solution

Here’s a fully detailed, reference-style solution guide for LeetCode 1609 - Even Odd Tree, following all your formatting rules:

Problem Understanding

The problem asks us to determine whether a given binary tree satisfies the Even-Odd Tree property. In other words, we need to validate two main conditions based on the level of the tree:

  1. For even-indexed levels (0, 2, 4, …), all node values must be odd and strictly increasing from left to right.
  2. For odd-indexed levels (1, 3, 5, …), all node values must be even and strictly decreasing from left to right.

The input is the root of a binary tree, where each node has an integer value. The output is a boolean: true if the tree satisfies the conditions, false otherwise.

The constraints indicate that the tree can be quite large, with up to 10^5 nodes, and values range from 1 to 10^6. This suggests that any solution must be linear in the number of nodes to run efficiently.

Important edge cases include:

  • A tree with only the root node. It must have an odd value for level 0.
  • Levels with a single node, which trivially satisfy the increasing/decreasing condition.
  • Levels where consecutive nodes violate the strictly increasing or decreasing order.
  • Levels where node parity is incorrect (odd on odd level or even on even level).

The problem guarantees a non-empty tree, so we do not need to handle None as the input root.

Approaches

The brute-force approach is straightforward: traverse the tree level by level (using BFS) and check for each level whether all values satisfy the parity condition and the strict ordering. For each node, we would need to compare its value with all other nodes on the same level. While correct, this naive approach is inefficient because it may involve repeated comparisons for each level.

The optimal approach leverages level-order traversal using a queue. At each level, we check each node in order:

  • Ensure node parity matches the level (odd for even-indexed, even for odd-indexed).
  • Ensure the values are strictly increasing or decreasing compared to the previous node on the same level.

This method is efficient because it visits each node exactly once and only maintains a small queue proportional to the current level’s width.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(n) Compares every node with all nodes in the level, inefficient for wide levels.
Optimal O(n) O(w) BFS with queue, where w is the maximum number of nodes at any level. Checks parity and ordering in one pass.

Algorithm Walkthrough

  1. Initialize a queue with the root node. This queue will help perform a level-order traversal (BFS).
  2. Set a variable level to 0 to track the current level index.
  3. While the queue is not empty, process each level as follows:

a. Record the number of nodes at the current level (level_size).

b. Initialize a variable prev_value for ordering checks. Set it to -inf for even levels and +inf for odd levels.

c. For each node in the current level:

i. Check parity: if the level is even, value must be odd; if the level is odd, value must be even. If not, return false.

ii. Check order: for even levels, value must be greater than prev_value; for odd levels, value must be smaller than prev_value. If not, return false.

iii. Update prev_value to the current node’s value.

iv. Enqueue the node’s left and right children if they exist. 4. Increment level after processing all nodes at the current level. 5. If all levels pass the checks, return true.

Why it works:

This BFS-based algorithm ensures that every level is checked in left-to-right order. By maintaining prev_value, we guarantee strict ordering. By checking parity per level, we enforce the even-odd property. Since BFS visits each node exactly once, the algorithm covers the entire tree efficiently.

Python Solution

# 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
from collections import deque
from typing import Optional

class Solution:
    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        
        queue = deque([root])
        level = 0
        
        while queue:
            level_size = len(queue)
            prev_value = float('-inf') if level % 2 == 0 else float('inf')
            
            for _ in range(level_size):
                node = queue.popleft()
                val = node.val
                
                # Check parity
                if level % 2 == 0 and val % 2 == 0:
                    return False
                if level % 2 == 1 and val % 2 == 1:
                    return False
                
                # Check order
                if level % 2 == 0 and val <= prev_value:
                    return False
                if level % 2 == 1 and val >= prev_value:
                    return False
                
                prev_value = val
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            level += 1
        
        return True

The code mirrors the algorithm: we perform BFS with a queue, check parity and strict ordering per level, and propagate children into the queue for the next level.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isEvenOddTree(root *TreeNode) bool {
    if root == nil {
        return true
    }
    
    queue := []*TreeNode{root}
    level := 0
    
    for len(queue) > 0 {
        levelSize := len(queue)
        var prevVal int
        if level % 2 == 0 {
            prevVal = -1
        } else {
            prevVal = 1000001
        }
        
        nextQueue := []*TreeNode{}
        
        for i := 0; i < levelSize; i++ {
            node := queue[i]
            val := node.Val
            
            if level % 2 == 0 && val % 2 == 0 {
                return false
            }
            if level % 2 == 1 && val % 2 == 1 {
                return false
            }
            
            if level % 2 == 0 && val <= prevVal {
                return false
            }
            if level % 2 == 1 && val >= prevVal {
                return false
            }
            
            prevVal = val
            
            if node.Left != nil {
                nextQueue = append(nextQueue, node.Left)
            }
            if node.Right != nil {
                nextQueue = append(nextQueue, node.Right)
            }
        }
        
        queue = nextQueue
        level++
    }
    
    return true
}

Go-specific notes: nil is used instead of None. We maintain a separate slice nextQueue to avoid issues with slicing while iterating. prevVal is initialized using the constraints of node values.

Worked Examples

Example 1: [1,10,4,3,null,7,9,12,8,6,null,null,2]

Level Nodes Parity Check Order Check Result
0 [1] odd N/A
1 [10,4] even 10 > 4? , but odd level decreases, 10 > 4
2 [3,7,9] odd 3 < 7 < 9
3 [12,8,6,2] even 12 > 8 > 6 > 2

Return true.

Example 2: [5,4,2,3,3,7]

Level Nodes Issue
2 [3,3,7] Values must be strictly increasing, 3 == 3

Return false.

Example 3: [5,9,1,3,5,7]

Level Nodes Issue
1 [9,1] Level 1 must have even values, 9 odd

Return false.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each node is visited exactly once in BFS.
Space O(w) Maximum width of a level stored in the queue, up to n/2 in worst case for a full binary tree.

The solution is linear in nodes and memory usage is proportional to the largest level.

Test Cases

# Provided examples
assert Solution().is