1609. Even Odd Tree - Leetcode Solution

Code Implementation

# 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
class Solution:
    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        q = deque()
        q.append(root)
        level = 0
        while q:
            size = len(q)
            prev_val = None
            for _ in range(size):
                node = q.popleft()
                # Check parity condition
                if level % 2 == 0:
                    # Even level: values must be odd and strictly increasing
                    if node.val % 2 == 0:
                        return False
                    if prev_val is not None and node.val <= prev_val:
                        return False
                else:
                    # Odd level: values must be even and strictly decreasing
                    if node.val % 2 == 1:
                        return False
                    if prev_val is not None and node.val >= prev_val:
                        return False
                prev_val = node.val
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            level += 1
        return True

// Definition for a binary tree node.
// struct TreeNode {
//     int val;
//     TreeNode *left;
//     TreeNode *right;
//     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
// };
#include <queue>
class Solution {
public:
    bool isEvenOddTree(TreeNode* root) {
        if (!root) return true;
        std::queue<TreeNode*> q;
        q.push(root);
        int level = 0;
        while (!q.empty()) {
            int size = q.size();
            int prev_val = (level % 2 == 0) ? INT_MIN : INT_MAX;
            for (int i = 0; i < size; ++i) {
                TreeNode* node = q.front(); q.pop();
                if (level % 2 == 0) {
                    // Even level: odd and strictly increasing
                    if (node->val % 2 == 0 || node->val <= prev_val)
                        return false;
                } else {
                    // Odd level: even and strictly decreasing
                    if (node->val % 2 == 1 || node->val >= prev_val)
                        return false;
                }
                prev_val = node->val;
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            ++level;
        }
        return true;
    }
};

// Definition for a binary tree node.
// public class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode(int x) { val = x; }
// }
import java.util.*;
class Solution {
    public boolean isEvenOddTree(TreeNode root) {
        if (root == null) return true;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int level = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            int prevVal = (level % 2 == 0) ? Integer.MIN_VALUE : Integer.MAX_VALUE;
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                if (level % 2 == 0) {
                    // Even level: odd, strictly increasing
                    if (node.val % 2 == 0 || node.val <= prevVal)
                        return false;
                } else {
                    // Odd level: even, strictly decreasing
                    if (node.val % 2 == 1 || node.val >= prevVal)
                        return false;
                }
                prevVal = node.val;
                if (node.left != null) q.offer(node.left);
                if (node.right != null) q.offer(node.right);
            }
            level++;
        }
        return true;
    }
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isEvenOddTree = function(root) {
    if (!root) return true;
    let queue = [root];
    let level = 0;
    while (queue.length > 0) {
        let size = queue.length;
        let prevVal = level % 2 === 0 ? -Infinity : Infinity;
        for (let i = 0; i < size; i++) {
            let node = queue.shift();
            if (level % 2 === 0) {
                // Even level: odd, strictly increasing
                if (node.val % 2 === 0 || node.val <= prevVal) return false;
            } else {
                // Odd level: even, strictly decreasing
                if (node.val % 2 === 1 || node.val >= prevVal) return false;
            }
            prevVal = node.val;
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        level++;
    }
    return true;
};

Problem Description

You are given the root of a binary tree. The tree is called an Even Odd Tree if it satisfies the following conditions:

Every node at an even-indexed level (starting from 0) has an odd integer value, and the values strictly increase from left to right across the level.
Every node at an odd-indexed level has an even integer value, and the values strictly decrease from left to right across the level.

Return true if the tree is an Even Odd Tree, and false otherwise.

Constraints:

Each node's value is a positive integer.
The tree may have up to 10⁵ nodes.
There is only one valid solution for each input tree.

Thought Process

To solve this problem, we need to check two properties at every level of the binary tree:

Parity: whether the node's value is odd or even, depending on the level.
Order: whether the values are strictly increasing (even levels) or strictly decreasing (odd levels).

The most straightforward way to achieve this is to traverse the tree level by level (using Breadth-First Search, or BFS), keeping track of the last value seen at each level to compare with the current node's value.
Initially, one might think of traversing the tree recursively, but since we need to process nodes in level order and compare adjacent values at each level, BFS is more suitable and efficient.
We also realize that, for each level, we only need to remember the previous value to check the strict order property, and the parity can be checked in constant time per node.

Solution Approach

We use Breadth-First Search (BFS) to traverse the tree level by level. Here’s the step-by-step approach:

Initialize a queue: Start by putting the root node in a queue. This queue will help us process nodes level by level.
Level traversal: For each level, process all nodes currently in the queue (which represents all nodes at that level).
Check parity and order: For each node at the current level:
- If the level is even (0, 2, 4, ...): check that the value is odd and strictly greater than the previous value at this level.
- If the level is odd (1, 3, 5, ...): check that the value is even and strictly less than the previous value at this level.
Queue children: Add the left and right children of the current node to the queue for the next level.
Repeat: Continue this process until all levels have been processed.
Return result: If all checks pass, return true. If any check fails, return false immediately.

We use a variable to keep track of the previous value at each level, resetting it at the start of each new level. For even levels, we initialize this to negative infinity (since we want strictly increasing values), and for odd levels to positive infinity (since we want strictly decreasing values).

Example Walkthrough

Let's walk through an example with the following tree:

Level 0: Nodes = [1]. Level is even, so value must be odd and strictly increasing. 1 is odd, so OK.
Level 1: Nodes = [10, 4]. Level is odd, so values must be even and strictly decreasing. 10 is even, OK. Next, 4 is even and less than 10, so OK.
Level 2: Nodes = [3, 7]. Level is even, so values must be odd and strictly increasing. 3 is odd, OK. Next, 7 is odd and greater than 3, so OK.

Since all levels satisfy the Even Odd Tree conditions, the function returns true.

Time and Space Complexity

Brute-force approach: If we tried to collect all nodes at each level, sort them, and check the order, this would be O(N log N) per level, which is inefficient for large trees.

Optimized BFS approach:

Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited exactly once, and all checks are O(1) per node.
Space Complexity: O(W), where W is the maximum width of the tree (maximum number of nodes at any level), due to the queue used in BFS.

This is optimal for this problem because we must examine every node to verify the properties.

Summary

The Even Odd Tree problem is efficiently solved using a level-order traversal (BFS), checking each level's node values for both parity and strict ordering. By keeping track of the previous value at each level and using a queue to traverse the tree, we ensure all constraints are met in a single pass. This approach is both intuitive and optimal, making good use of BFS to process the tree level by level.

AlgoMap.io

Want Help Cracking FAANG?