Even Odd Tree - Practice Coding Problems

Even Odd Tree - Problem

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.

Input & Output

Example 1 — Valid Even-Odd Tree

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

› Output: true

💡 Note: Level 0: [1] (odd, single node ✓), Level 1: [10,4] (even, 10>4 decreasing ✓), Level 2: [3,7,9] (odd, 3<7<9 increasing ✓), Level 3: [12,8,6,2] (even, 12>8>6>2 decreasing ✓)

Example 2 — Invalid Ordering

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

› Output: false

💡 Note: Level 0: [5] (odd ✓), Level 1: [4,2] (even, 4>2 decreasing ✓), Level 2: [3,3,7] (odd but 3=3 not strictly increasing ✗)

Example 3 — Invalid Parity

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

› Output: false

💡 Note: Level 0: [5] (odd ✓), Level 1: [9,1] (should be even but both are odd ✗)

Constraints

The number of nodes in the tree is in the range [1, 10⁵]
1 ≤ Node.val ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with nodes at different levels

Level Rules

Even levels: odd values increasing, Odd levels: even values decreasing

Validation

Check each level against its constraints

Key Takeaway

🎯 Key Insight: Use BFS to validate level constraints immediately as you traverse each level

Asked in

M Microsoft 15 A Amazon 12 F Facebook 8

The key insight is to use BFS level-order traversal to validate each level's constraints immediately. For even levels, check all values are odd and strictly increasing; for odd levels, check all values are even and strictly decreasing. Best approach is BFS with single pass. Time: O(n), Space: O(w) where w is tree width.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force DFS	O(n)	O(n)	Use DFS to collect all values at each level, then validate constraints
BFS Level-Order Traversal	O(n)	O(w)	Use BFS to process each level and validate constraints in single pass

Brute Force DFS — Algorithm Steps

Step 1: Use DFS to collect values at each level
Step 2: For each level, check value parity and ordering constraints

Visualization

Tap to expand

Step-by-Step Walkthrough

DFS Traversal

Traverse tree and group values by level

Level Validation

Check each level's parity and ordering rules

Result

Return true if all levels pass validation

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void dfs(struct TreeNode* node, int level, int levels[][1000], int* levelSizes, int* maxLevel) {
    if (!node) return;
    
    if (level > *maxLevel) *maxLevel = level;
    levels[level][levelSizes[level]++] = node->val;
    
    dfs(node->left, level + 1, levels, levelSizes, maxLevel);
    dfs(node->right, level + 1, levels, levelSizes, maxLevel);
}

bool solution(struct TreeNode* root) {
    if (!root) return true;
    
    int levels[1000][1000];
    int levelSizes[1000] = {0};
    int maxLevel = -1;
    
    dfs(root, 0, levels, levelSizes, &maxLevel);
    
    for (int level = 0; level <= maxLevel; level++) {
        if (levelSizes[level] == 0) continue;
        
        if (level % 2 == 0) {
            // Even level: odd values, strictly increasing
            for (int i = 0; i < levelSizes[level]; i++) {
                if (levels[level][i] % 2 == 0) return false;
            }
            for (int i = 1; i < levelSizes[level]; i++) {
                if (levels[level][i] <= levels[level][i-1]) return false;
            }
        } else {
            // Odd level: even values, strictly decreasing
            for (int i = 0; i < levelSizes[level]; i++) {
                if (levels[level][i] % 2 == 1) return false;
            }
            for (int i = 1; i < levelSizes[level]; i++) {
                if (levels[level][i] >= levels[level][i-1]) return false;
            }
        }
    }
    
    return true;
}

int main() {
    // For simplicity in C, assuming a small test case
    struct TreeNode* root = createNode(1);
    root->left = createNode(10);
    root->right = createNode(4);
    root->left->left = createNode(3);
    root->right->left = createNode(7);
    root->right->right = createNode(9);
    root->left->left->left = createNode(12);
    root->left->left->right = createNode(8);
    root->right->left->left = createNode(6);
    root->right->right->right = createNode(2);
    
    bool result = solution(root);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node once during DFS traversal, then validate each level

✓ Linear Growth

Space Complexity

O(n)

Store all node values grouped by level, plus recursion stack depth

⚡ Linearithmic Space

32.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler