LeetCode Solutions Blog

Even Odd Tree

Number: 1731

Difficulty: Medium

Paid? No

Problem Description

Given a binary tree, determine whether it is an Even-Odd Tree. The tree is structured into levels where:

Even-indexed levels (starting at 0) must contain odd integer values in strictly increasing order from left to right.
Odd-indexed levels must contain even integer values in strictly decreasing order from left to right. Return true if the tree meets these conditions; otherwise, return false.

Key Insights

Use a level-order (BFS) traversal to process nodes level by level.
At even-indexed levels, ensure each value is odd and each subsequent value is larger than the previous.
At odd-indexed levels, ensure each value is even and each subsequent value is smaller than the previous.
Edge cases include verifying node values are of the correct parity at their level.
The properties must be maintained even with null children in the tree representation.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the tree. Space Complexity: O(n), which is the space for the queue used in the level order traversal (in the worst-case scenario of a skewed tree or complete tree level).

Solution

We perform a breadth-first search (BFS) on the tree to evaluate each level’s values. For every level:

If the level is even-indexed, we check that every node’s value is odd and that the values are strictly increasing.
If the level is odd-indexed, we check that every node’s value is even and that the values are strictly decreasing. We update the queue with the next level’s nodes and verify the conditions as we go. If any condition is violated, we return false immediately. If all levels comply, we return true at the end.

Code Solutions

# 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

def isEvenOddTree(root: TreeNode) -> bool:
    from collections import deque
    
    # Initialize the queue with the root along with the level information
    queue = deque([root])
    level = 0  # starting with level 0
    
    while queue:
        level_size = len(queue)
        # Initialize a variable to store the previous value to check ordering
        if level % 2 == 0:
            prev_val = float('-inf')  # For increasing order in even-indexed levels.
        else:
            prev_val = float('inf')  # For decreasing order in odd-indexed levels.
        
        for _ in range(level_size):
            node = queue.popleft()
            
            # Check for correct parity based on the level index
            if level % 2 == 0:
                # At even-indexed levels, value must be odd
                if node.val % 2 == 0:
                    return False
                # Check strictly increasing order
                if node.val <= prev_val:
                    return False
            else:
                # At odd-indexed levels, value must be even
                if node.val % 2 != 0:
                    return False
                # Check strictly decreasing order
                if node.val >= prev_val:
                    return False
            
            # Update previous value for order checking
            prev_val = node.val
            
            # Append children nodes to the queue for the next level
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        # Move to the next level
        level += 1

    # If all levels pass the conditions, return True
    return True