Watch 10 video solutions for Even Odd Tree, a medium level problem involving Tree, Breadth-First Search, Binary Tree. This walkthrough by NeetCodeIO has 14,763 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
A binary tree is named Even-Odd if it meets the following conditions:
0, its children are at level index 1, their children are at level index 2, etc.Given the root of a binary tree, return true if the binary tree is Even-Odd, otherwise return false.
Example 1:
Input: root = [1,10,4,3,null,7,9,12,8,6,null,null,2] Output: true Explanation: The node values on each level are: Level 0: [1] Level 1: [10,4] Level 2: [3,7,9] Level 3: [12,8,6,2] Since levels 0 and 2 are all odd and increasing and levels 1 and 3 are all even and decreasing, the tree is Even-Odd.
Example 2:
Input: root = [5,4,2,3,3,7] Output: false Explanation: The node values on each level are: Level 0: [5] Level 1: [4,2] Level 2: [3,3,7] Node values in level 2 must be in strictly increasing order, so the tree is not Even-Odd.
Example 3:
Input: root = [5,9,1,3,5,7] Output: false Explanation: Node values in the level 1 should be even integers.
Constraints:
[1, 105].1 <= Node.val <= 106Problem Overview: You are given the root of a binary tree. The tree must follow strict level rules: nodes at even-indexed levels contain odd values in strictly increasing order, while nodes at odd-indexed levels contain even values in strictly decreasing order. The task is to verify whether the entire tree satisfies these constraints.
Approach 1: Level Order Traversal (BFS) (Time: O(n), Space: O(w))
This approach uses a queue to perform level order traversal, which naturally processes nodes level by level. For each level, track the previous value seen and enforce two constraints: parity (odd vs even) and ordering (increasing or decreasing). On even levels, each value must be odd and strictly greater than the previous value. On odd levels, each value must be even and strictly smaller than the previous value. Because every node is visited exactly once and checked with constant-time comparisons, the total time complexity is O(n), where n is the number of nodes. The queue may hold up to the width of the tree, giving O(w) space complexity.
This is the most intuitive method because level constraints map directly to breadth-first traversal. If you're comfortable with Breadth-First Search on a binary tree, the implementation is straightforward.
Approach 2: Depth First Search (DFS) with Level Tracking (Time: O(n), Space: O(h))
Instead of processing nodes level by level, DFS explores the tree recursively while tracking the current depth. Maintain a structure (usually a vector or map) storing the last value seen at each level. When visiting a node, check the parity rule for that level and compare its value with the stored previous value to ensure the correct ordering. If the constraint fails, terminate early.
DFS still visits each node once, so the time complexity remains O(n). The recursion stack grows up to the height of the tree, resulting in O(h) auxiliary space. This approach works well when you prefer recursive traversal patterns common in tree problems.
Recommended for interviews: The BFS level order traversal is the expected approach. The problem explicitly defines rules per level, and BFS processes nodes exactly in that order, making the validation logic simple and readable. Showing the DFS version demonstrates deeper understanding of tree traversal patterns, but BFS is typically the cleaner interview solution.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Level Order Traversal (BFS) | O(n) | O(w) | Best when validating constraints defined per tree level |
| DFS with Level Tracking | O(n) | O(h) | Useful when implementing recursive tree traversal patterns |