Even Odd Tree

Med

#1479Time: 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.

Algorithms

Breadth-First Search

Data structures

Tree Binary Tree

Prompt

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:

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:

The number of nodes in the tree is in the range [1, 10⁵].
1 <= Node.val <= 10⁶

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1import java.util.ArrayList;2import java.util.List;3 4/**5 * Definition for a binary tree node.6 * public class TreeNode {7 *     int val;8 *     TreeNode left;9 *     TreeNode right;10 *     TreeNode() {}11 *     TreeNode(int val) { this.val = val; }12 *     TreeNode(int val, TreeNode left, TreeNode right) {13 *         this.val = val;14 *         this.left = left;15 *         this.right = right;16 *     }17 * }18 */19class Solution {20    // List to store the last seen value at each level21    private List<Integer> lastValues = new ArrayList<>();22 23    public boolean isEvenOddTree(TreeNode root) {24        return dfs(root, 0);25    }26 27    private boolean dfs(TreeNode node, int level) {28        if (node == null) {29            return true;30        }31 32        // Condition 1: Parity check based on level33        // If level is even, value must be odd. If level is odd, value must be even.34        // This is equivalent to checking if level and value have different parity.35        if (level % 2 == node.val % 2) {36            return false;37        }38 39        // Condition 2: Order check40        // If this is the first node we've seen at this level41        if (level >= lastValues.size()) {42            lastValues.add(node.val);43        } else {44            int prevVal = lastValues.get(level);45            // Even level: must be strictly increasing46            if (level % 2 == 0) {47                if (node.val <= prevVal) {48                    return false;49                }50            } 51            // Odd level: must be strictly decreasing52            else {53                if (node.val >= prevVal) {54                    return false;55                }56            }57            // Update the last value for the current level58            lastValues.set(level, node.val);59        }60 61        // Recurse for children62        return dfs(node.left, level + 1) && dfs(node.right, level + 1);63    }64}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1import java.util.LinkedList;2import java.util.Queue;3 4/**5 * Definition for a binary tree node.6 * public class TreeNode {7 *     int val;8 *     TreeNode left;9 *     TreeNode right;10 *     TreeNode() {}11 *     TreeNode(int val) { this.val = val; }12 *     TreeNode(int val, TreeNode left, TreeNode right) {13 *         this.val = val;14 *         this.left = left;15 *         this.right = right;16 *     }17 * }18 */19class Solution {20    public boolean isEvenOddTree(TreeNode root) {21        if (root == null) {22            return true;23        }24 25        Queue<TreeNode> queue = new LinkedList<>();26        queue.offer(root);27        int level = 0;28 29        while (!queue.isEmpty()) {30            int size = queue.size();31            // For even levels, we need increasing order, so prevVal starts small.32            // For odd levels, we need decreasing order, so prevVal starts large.33            int prevVal = (level % 2 == 0) ? Integer.MIN_VALUE : Integer.MAX_VALUE;34 35            for (int i = 0; i < size; i++) {36                TreeNode node = queue.poll();37                int val = node.val;38 39                if (level % 2 == 0) { // Even-indexed level40                    // Value must be odd and strictly increasing.41                    if (val % 2 == 0 || val <= prevVal) {42                        return false;43                    }44                } else { // Odd-indexed level45                    // Value must be even and strictly decreasing.46                    if (val % 2 != 0 || val >= prevVal) {47                        return false;48                    }49                }50                51                prevVal = val;52 53                if (node.left != null) {54                    queue.offer(node.left);55                }56                if (node.right != null) {57                    queue.offer(node.right);58                }59            }60            level++;61        }62 63        return true;64    }65}

Complexity

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).

Trade-offs

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.

Solutions

Solution

1/** * 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 ; } }

1/** * 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 ; } };

1# 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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem