Even Odd Tree

Medium
1953.

Even Odd Tree

Even Odd Tree is a medium coding problem on breadth-first search and trees, asked in Amazon and Bloomberg interviews.

Number the levels of a binary tree from 0 at the root. The tree is an Even-Odd tree when:

  • on every even-indexed level, all values are odd and strictly increasing from left to right;
  • on every odd-indexed level, all values are even and strictly decreasing from left to right.

Given the root, return true if the tree is Even-Odd, and false otherwise.

Example 1

Input
root = [1,10,4,3,null,7,9,12,8,6,null,null,2]
Output
true
Explanation
Level 0: [1]; level 1: [10, 4] even and decreasing; level 2: [3, 7, 9] odd and increasing; level 3: [12, 8, 6, 2] even and decreasing.

Example 2

Input
root = [5,4,2,3,3,7]
Output
false
Explanation
Level 2 is [3, 3, 7]: odd, but 3, 3 is not strictly increasing.

Example 3

Input
root = [5,9,1,3,5,7]
Output
false
Explanation
Level 1 holds the odd values 9 and 1, but an odd-indexed level needs even values.

Example 4

Input
root = [1]
Output
true
Explanation
A lone odd root satisfies every rule.

Constraints

  • 1 <= number of nodes <= 10^5
  • 1 <= Node.val <= 10^6
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * 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) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Even Odd Tree — Solution in Python, Java & C++

Even Odd Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Even Odd Tree is a medium coding problem on breadth-first search and trees, asked in Amazon and Bloomberg interviews.

  • Difficulty: Medium
  • Topics: Breadth-First Search, Trees
  • Asked at: Amazon, Bloomberg
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Number the levels of a binary tree from 0 at the root. The tree is an Even-Odd tree when:

  • on every even-indexed level, all values are odd and strictly increasing from left to right;
  • on every odd-indexed level, all values are even and strictly decreasing from left to right.

Given the root, return true if the tree is Even-Odd, and false otherwise.

Example 1

Input: root = [1,10,4,3,null,7,9,12,8,6,null,null,2]
Output: true
Explanation: Level 0: [1]; level 1: [10, 4] even and decreasing; level 2: [3, 7, 9] odd and increasing; level 3: [12, 8, 6, 2] even and decreasing.

Example 2

Input: root = [5,4,2,3,3,7]
Output: false
Explanation: Level 2 is [3, 3, 7]: odd, but 3, 3 is not strictly increasing.

Example 3

Input: root = [5,9,1,3,5,7]
Output: false
Explanation: Level 1 holds the odd values 9 and 1, but an odd-indexed level needs even values.

Example 4

Input: root = [1]
Output: true
Explanation: A lone odd root satisfies every rule.

Constraints

  • 1 <= number of nodes <= 10^5
  • 1 <= Node.val <= 10^6

Hints for Even Odd Tree

  1. Hint 1

    Every rule is about one level read left to right — so read the tree level by level.

  2. Hint 2

    A breadth-first walk delivers each level's nodes in left-to-right order.

  3. Hint 3

    Within a level, check each value's parity and compare it with the previous value on the same level; restart the comparison at every new level.

How to solve Even Odd Tree

Breadth-first order visits each level left to right, so each rule becomes a check against the previous node of the same level.

Approach

  1. Put the root in a queue; set level = 0.
  2. For each level, walk its nodes in order keeping prev, the previous value on this level.
  3. On an even level, fail if a value is even or not greater than prev; on an odd level, fail if a value is odd or not smaller than prev.
  4. Enqueue the children, move to the next level; return true if every level passes.

Why it works

Taking exactly the queued nodes in each round yields one complete level in left-to-right order, so comparing neighbours in that order checks strict monotonicity for the whole level, and the parity test checks every node.

Complexity

  • Time — O(n)
  • Space — O(w), w the widest level

Pitfalls

  • Strictly increasing and decreasing: equal neighbours fail.
  • Reset prev at the start of each level — comparing with the last node of the previous level is wrong.

Reference solution

Python

from typing import Optional

def isEvenOddTree(root: Optional[TreeNode]) -> bool:
    level = [root]
    depth = 0
    while level:
        prev = None
        nxt = []
        for node in level:
            v = node.val
            if depth % 2 == 0:
                if v % 2 == 0 or (prev is not None and v <= prev):
                    return False
            else:
                if v % 2 == 1 or (prev is not None and v >= prev):
                    return False
            prev = v
            if node.left:
                nxt.append(node.left)
            if node.right:
                nxt.append(node.right)
        level = nxt
        depth += 1
    return True

Java

public static boolean isEvenOddTree(TreeNode root) {
    List<TreeNode> level = new ArrayList<>();
    level.add(root);
    int depth = 0;
    while (!level.isEmpty()) {
        List<TreeNode> next = new ArrayList<>();
        for (int i = 0; i < level.size(); i++) {
            int v = level.get(i).val;
            if (depth % 2 == 0) {
                if (v % 2 == 0 || (i > 0 && v <= level.get(i - 1).val)) return false;
            } else if (v % 2 == 1 || (i > 0 && v >= level.get(i - 1).val)) return false;
            if (level.get(i).left != null) next.add(level.get(i).left);
            if (level.get(i).right != null) next.add(level.get(i).right);
        }
        level = next;
        depth++;
    }
    return true;
}

C++

bool isEvenOddTree(TreeNode* root) {
    vector<TreeNode*> level{root};
    int depth = 0;
    while (!level.empty()) {
        vector<TreeNode*> next;
        for (size_t i = 0; i < level.size(); i++) {
            int v = level[i]->val;
            if (depth % 2 == 0) {
                if (v % 2 == 0 || (i > 0 && v <= level[i - 1]->val)) return false;
            } else if (v % 2 == 1 || (i > 0 && v >= level[i - 1]->val)) return false;
            if (level[i]->left) next.push_back(level[i]->left);
            if (level[i]->right) next.push_back(level[i]->right);
        }
        level.swap(next);
        depth++;
    }
    return true;
}

JavaScript

var isEvenOddTree = function(root) {
    var level = [root], depth = 0;
    while (level.length > 0) {
        var next = [];
        for (var i = 0; i < level.length; i++) {
            var v = level[i].val;
            if (depth % 2 === 0) {
                if (v % 2 === 0 || (i > 0 && v <= level[i - 1].val)) return false;
            } else if (v % 2 === 1 || (i > 0 && v >= level[i - 1].val)) return false;
            if (level[i].left !== null) next.push(level[i].left);
            if (level[i].right !== null) next.push(level[i].right);
        }
        level = next;
        depth++;
    }
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 156 breadth-first search problems · the whole catalogue

Learn the technique: Breadth-First Search (BFS) · Binary Trees and Tree Traversals