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^51 <= Node.val <= 10^6
Hints for Even Odd Tree
Hint 1
Every rule is about one level read left to right — so read the tree level by level.
Hint 2
A breadth-first walk delivers each level's nodes in left-to-right order.
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
- Put the root in a queue; set
level = 0. - For each level, walk its nodes in order keeping
prev, the previous value on this level. - 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 thanprev. - 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
prevat 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 TrueJava
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