# Even Odd Tree
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/even-odd-tree)
Canonical: https://scaleengineer.com/dsa/problems/even-odd-tree
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree, Binary 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`_._

**Example 1:**

![](https://assets.glich.co/dsa/even-odd-tree/image0.png) 

**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:**

![](https://assets.glich.co/dsa/even-odd-tree/image1.png) 

**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:**

![](https://assets.glich.co/dsa/even-odd-tree/image2.png) 

**Input:** root = [5,9,1,3,5,7]
**Output:** false
**Explanation:** Node values in the level 1 should be even integers.

**Constraints:**

* The number of nodes in the tree is in the range `[1, 105]`.
* `1 <= Node.val <= 106`

# Approaches
## Depth-First Search (DFS)
This approach uses a recursive Depth-First Search (DFS) to traverse the tree. To enforce the ordering constraints (strictly increasing/decreasing) at each level, we need to keep track of the last value encountered at every level. A list can be used for this purpose, where the index corresponds to the tree level. A pre-order traversal ensures that nodes at a given level are processed from left to right.
**Time:** O(N), where N is the number of nodes in the tree. Each node is visited exactly once. · **Space:** O(H), where H is the height of the tree. This space is used by the recursion stack and the `lastValues` list. In the worst case of a skewed tree, H can be equal to N (the number of nodes), leading to O(N) space complexity.
**Pros:** Conceptually straightforward implementation of tree traversal.
**Cons:** Can cause a `StackOverflowError` for very deep trees due to the depth of recursion.; The space complexity depends on the tree's height, which can be O(N) for skewed trees, making it less memory-efficient in such cases compared to BFS.
### Explanation
We perform a pre-order traversal (`root`, `left`, `right`) of the tree. This ensures that for any given level, we visit the nodes from left to right.
A helper function, say `dfs(node, level)`, is used. It takes the current node and its level as arguments.
We maintain a list, `lastValues`, accessible by the recursive calls, where `lastValues.get(level)` stores the value of the previously visited node at that `level`.

```java
import java.util.ArrayList;
import java.util.List;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // List to store the last seen value at each level
    private List<Integer> lastValues = new ArrayList<>();

    public boolean isEvenOddTree(TreeNode root) {
        return dfs(root, 0);
    }

    private boolean dfs(TreeNode node, int level) {
        if (node == null) {
            return true;
        }

        // Condition 1: Parity check based on level
        // If level is even, value must be odd. If level is odd, value must be even.
        // This is equivalent to checking if level and value have different parity.
        if (level % 2 == node.val % 2) {
            return false;
        }

        // Condition 2: Order check
        // If this is the first node we've seen at this level
        if (level >= lastValues.size()) {
            lastValues.add(node.val);
        } else {
            int prevVal = lastValues.get(level);
            // Even level: must be strictly increasing
            if (level % 2 == 0) {
                if (node.val <= prevVal) {
                    return false;
                }
            } 
            // Odd level: must be strictly decreasing
            else {
                if (node.val >= prevVal) {
                    return false;
                }
            }
            // Update the last value for the current level
            lastValues.set(level, node.val);
        }

        // Recurse for children
        return dfs(node.left, level + 1) && dfs(node.right, level + 1);
    }
}
```
### Algorithm
- Use a recursive helper function `dfs(node, level)`.
- Maintain a list, `lastValues`, where `lastValues.get(level)` stores the value of the previously visited node at that `level`.
- The traversal must be pre-order (`root`, `left`, `right`) to ensure nodes at the same level are visited from left to right.
- **Base Case:** If `node` is `null`, return `true`.
- **Parity Check:**
  - If `level` is even, `node.val` must be odd. If not, return `false`.
  - If `level` is odd, `node.val` must be even. If not, return `false`.
- **Order Check:**
  - If it's the first node at this `level` (i.e., `level >= lastValues.size()`), add its value to `lastValues`.
  - Otherwise, get `prevVal = lastValues.get(level)`.
  - For an even `level`, check if `node.val > prevVal`. If not, return `false`.
  - For an odd `level`, check if `node.val < prevVal`. If not, return `false`.
  - If the check passes, update `lastValues.set(level, node.val)`.
- **Recursive Step:** Return `true` only if the recursive calls for both left and right children, `dfs(node.left, level + 1)` and `dfs(node.right, level + 1)`, return `true`.

## Breadth-First Search (BFS)
This is the most natural and generally more robust approach for problems involving level-by-level processing of a tree. We traverse the tree one level at a time using a queue (Breadth-First Search), and at each level, we verify the Even-Odd tree conditions.
**Time:** O(N), where N is the number of nodes. Each node is enqueued and dequeued exactly once. · **Space:** O(W), where W is the maximum width of the tree. This is the maximum number of nodes that can be in the queue at any one time. In the worst case of a complete binary tree, the last level contains roughly N/2 nodes, making the space complexity O(N).
**Pros:** Iterative approach avoids recursion and the risk of `StackOverflowError` on deep trees.; Directly processes the tree level by level, which aligns perfectly with the problem statement.; Generally more space-efficient for deep, narrow trees compared to DFS.
**Cons:** Can be less space-efficient than DFS for very wide and shallow trees, as the queue might hold a large number of nodes.
### Explanation
We use a queue to perform a standard level-order traversal. A variable `level` keeps track of the current level index (starting from 0).
For each level, we process all nodes currently in the queue. We also keep track of the previous node's value (`prevVal`) within that level to check the ordering condition.

```java
import java.util.LinkedList;
import java.util.Queue;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isEvenOddTree(TreeNode root) {
        if (root == null) {
            return true;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int level = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            // For even levels, we need increasing order, so prevVal starts small.
            // For odd levels, we need decreasing order, so prevVal starts large.
            int prevVal = (level % 2 == 0) ? Integer.MIN_VALUE : Integer.MAX_VALUE;

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                int val = node.val;

                if (level % 2 == 0) { // Even-indexed level
                    // Value must be odd and strictly increasing.
                    if (val % 2 == 0 || val <= prevVal) {
                        return false;
                    }
                } else { // Odd-indexed level
                    // Value must be even and strictly decreasing.
                    if (val % 2 != 0 || val >= prevVal) {
                        return false;
                    }
                }
                
                prevVal = val;

                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            level++;
        }

        return true;
    }
}
```
### Algorithm
- Initialize a `Queue` and add the `root` node.
- Initialize a `level` counter to 0.
- Loop while the queue is not empty.
  - Get the number of nodes at the current level, `size = queue.size()`.
  - Initialize `prevVal`. For even levels, initialize to `Integer.MIN_VALUE`. For odd levels, initialize to `Integer.MAX_VALUE`.
  - Loop `size` times to process all nodes of the current level:
    - Dequeue a `node`.
    - **Even level:** Check if `node.val` is odd and strictly greater than `prevVal`. If not, return `false`.
    - **Odd level:** Check if `node.val` is even and strictly less than `prevVal`. If not, return `false`.
    - Update `prevVal = node.val`.
    - Enqueue the non-null left and right children of the `node`.
  - After processing the level, increment the `level` counter.
- If the main loop completes, return `true`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public boolean isEvenOddTree ( TreeNode root ) { Queue < TreeNode > que = new LinkedList < > (); que . add ( root ); que . add ( null ); int res = 1 ; int c = 0 ; int prev = 0 ; while (! que . isEmpty ()) { if ( res % 2 == 0 ) prev = Integer . MAX_VALUE ; else prev = Integer . MIN_VALUE ; while ( que . peek () != null ) { if ( que . peek (). val % 2 != res % 2 ) { return false ; } if ( res % 2 == 0 && prev <= que . peek (). val ) { return false ; } if ( res % 2 != 0 && prev >= que . peek (). val ) return false ; if ( que . peek (). left != null ) que . add ( que . peek (). left ); if ( que . peek (). right != null ) que . add ( que . peek (). right ); prev = que . poll (). val ; } que . poll (); if ( que . isEmpty ()) { break ; } res ++; que . add ( null ); } return true ; } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool isEvenOddTree ( TreeNode * root ) { int even = 1 ; queue < TreeNode *> q { { root } }; while ( ! q . empty ()) { int prev = even ? 0 : 1e6 ; for ( int n = q . size (); n ; -- n ) { root = q . front (); q . pop (); if ( even && ( root -> val % 2 == 0 || prev >= root -> val )) return false ; if ( ! even && ( root -> val % 2 == 1 || prev <= root -> val )) return false ; prev = root -> val ; if ( root -> left ) q . push ( root -> left ); if ( root -> right ) q . push ( root -> right ); } even ^= 1 ; } return true ; } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def isEvenOddTree ( self , root : Optional [ TreeNode ]) -> bool : even = 1 q = deque ([ root ]) while q : prev = 0 if even else inf for _ in range ( len ( q )): root = q . popleft () if even and ( root . val % 2 == 0 or prev >= root . val ): return False if not even and ( root . val % 2 == 1 or prev <= root . val ): return False prev = root . val if root . left : q . append ( root . left ) if root . right : q . append ( root . right ) even ^= 1 return True
```