Even Odd Tree
Medium · Trees · Tree · Breadth-First Search · Binary Tree
Problem
Number the levels of a binary tree from the root: the root's level has index 0, its children's level index 1, and so on.
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 an Even-Odd tree, and False otherwise. "Left to right" means across the whole level, even between nodes with different parents.
The tree is given in level order, with None for a missing child. from_level([5,8,2]) builds it and to_level(root) turns it back into a list.
Examples
Input: root = [1,10,4,3,None,7,9,12,8,6,None,None,2] Output: True
Levels: [1] odd; [10,4] even, decreasing; [3,7,9] odd, increasing; [12,8,6,2] even, decreasing.
Input: root = [5,4,2,3,3,7] Output: False
Level 2 is [3,3,7]: it does not strictly increase from 3 to 3.
Input: root = [2] Output: False
Level 0 must hold odd values.
Constraints
- 1 <= number of nodes <= 10^5
- 1 <= Node.val <= 10^6
Approaches
- Baseline: collect every level, then check — time O(n), space O(n)
Follow-up
A depth-first walk can do it in O(h) memory: keep one "last value seen" per depth, and visit left children before right ones. The use cases ask for the first level that breaks the rule, and drop parity in favor of a level order that increases throughout.
Related problems
Start free on Cariara · Coding problems · System design studio
