We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

Even Odd Tree

Difficulty: Medium

Problem Description

A binary tree is named Even-Odd if it meets the following conditions:

The root of the binary tree is at level index 0, its children are at level index 1, their children are at level index 2, etc.
For every even-indexed level, all nodes at the level have odd integer values in strictly increasing order (from left to right).
For every odd-indexed level, all nodes at the level have even integer values in strictly decreasing order (from left to right).

Given the root of a binary tree, return true if the binary tree is Even-Odd, otherwise return false.

Key Insights

Use level-order traversal (BFS) to explore nodes level by level.
Check values based on their level index: odd or even, and ensure the required order (increasing or decreasing).
Maintain the previous value for comparison to ensure strict ordering.

Space and Time Complexity

Time Complexity: O(n) - where n is the number of nodes in the tree, as each node is visited exactly once.

Space Complexity: O(m) - where m is the maximum width of the tree, as we store nodes at each level in a queue during BFS.

Solution

The solution involves performing a level-order traversal of the binary tree using a queue. For each level:

Check if the level index is even or odd.
Depending on the index, verify that all node values are either odd (for even levels) or even (for odd levels).
Ensure the values are in the required order (strictly increasing for even levels and strictly decreasing for odd levels).
If any condition fails, return false; otherwise, return true after checking all levels.

Code Solutions

from collections import deque

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:
    if not root:
        return True
    
    queue = deque([root])
    level = 0
    
    while queue:
        level_size = len(queue)
        prev_value = None
        
        for _ in range(level_size):
            node = queue.popleft()
            
            # Check for even-indexed level
            if level % 2 == 0:
                if node.val % 2 == 0 or (prev_value is not None and node.val <= prev_value):
                    return False
            # Check for odd-indexed level
            else:
                if node.val % 2 != 0 or (prev_value is not None and node.val >= prev_value):
                    return False
            
            prev_value = node.val
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        level += 1
    
    return True

← Back to All Questions