Skip to main content
Talentd

Even Odd Tree - Solution & Explanation

MediumTreeBreadth-First SearchBinary Tree15 min readAsked at: Amazon, Meta, Bloomberg
Practice this problem

Problem Statement

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, 105].
  • 1 <= Node.val <= 106

Approach Overview

Problem 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 1: Level Order Traversal (BFS)

This approach employs a breadth-first search (BFS) to traverse the binary tree level by level. We maintain a queue to keep track of the nodes at each level, examining their values to ensure compliance with the Even-Odd criteria:

  • For even-indexed levels, node values should be odd and in strictly increasing order.
  • For odd-indexed levels, node values should be even and in strictly decreasing order.

The solution employs a queue for level-order traversal. On each level, it examines the nodes' values to ensure conformity with the problem's even-odd level requirements.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(N), where N is the number of nodes, as each node is inspected once.
Space Complexity: O(M), where M is the maximum number of nodes at any level in the tree (width of the tree), due to the BFS queue.

Try this approach in the editor →

Approach 2: Depth First Search (DFS) with Level Tracking

This approach applies a depth-first search (DFS) method, maintaining level information to confirm constraints. We use recursion to explore the tree, while an array stores the last value seen on each level to validate order constraints.

In the C++ solution, we use a recursive function to perform DFS while maintaining the last meaningful value for level validation in an array. This array ensures all nodes at each level meet the Even-Odd Tree constraints.

Code

C++Java

C++

Java

Complexity

Time Complexity: O(N), with N being the number of nodes.
Space Complexity: O(H), where H is the height of the tree, accounting for recursion stack and the array storing last values at each level.

Try this approach in the editor →

Approach 3: BFS

BFS traverses level by level. Each level is judged by its parity. The node values at each level are either all even or all odd, and they are strictly increasing or decreasing.

The time complexity is O(n), and the space complexity is O(n), where n is the number of nodes in the binary tree.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Approach 4: DFS

DFS performs a pre-order traversal of the binary tree, and similarly judges whether it meets the conditions based on the parity of the layer where the node is located. During the traversal, a hash table is used to record the node value that was most recently visited at each layer.

The time complexity is O(n), and the space complexity is O(n), where n is the number of nodes in the binary tree.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Level Order Traversal (BFS)

Time Complexity: O(N), where N is the number of nodes, as each node is inspected once.
Space Complexity: O(M), where M is the maximum number of nodes at any level in the tree (width of the tree), due to the BFS queue.

Depth First Search (DFS) with Level Tracking

Time Complexity: O(N), with N being the number of nodes.
Space Complexity: O(H), where H is the height of the tree, accounting for recursion stack and the array storing last values at each level.

BFS—
DFS—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Level Order Traversal (BFS)O(n)O(w)Best when validating constraints defined per tree level
DFS with Level TrackingO(n)O(h)Useful when implementing recursive tree traversal patterns

Video Solution

Even Odd Tree - Leetcode 1609 - Python • NeetCodeIO • 14,839 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Even Odd Tree easy or hard?
Even Odd Tree is rated Medium difficulty. The logic itself is straightforward once you recognize it as a level-order traversal problem, but careful handling of parity checks and strict ordering conditions is required to avoid edge-case bugs.
Even Odd Tree Python/Java solution
Python and Java solutions typically use a queue for level order traversal. For each level, initialize a previous value and verify both parity (odd/even rule) and ordering (increasing or decreasing). If any node violates the rule, return false immediately; otherwise continue until all nodes are validated.
How to solve Even Odd Tree in O(n)?
Traverse the tree once and validate level constraints while visiting nodes. Using BFS, process nodes level by level with a queue, checking that even levels contain odd values in strictly increasing order and odd levels contain even values in strictly decreasing order. Since each node is processed once, the algorithm runs in O(n) time.
What is the best approach for Even Odd Tree?
Level Order Traversal (BFS) is the most practical approach. The problem defines constraints for each level of the tree, and BFS processes nodes exactly level by level. While traversing, you track the previous value in the level and enforce parity and ordering rules. This yields O(n) time and O(w) space complexity.
Is Even Odd Tree asked at Google/Amazon/Meta?
Tree validation and level-order traversal problems frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact problem may not always appear, the pattern of checking constraints during BFS traversal is a common interview theme.
What data structure is used in Even Odd Tree?
The most common implementation uses a queue to perform Breadth-First Search (BFS) on the binary tree. The queue stores nodes of the current level while enforcing ordering constraints. The DFS alternative uses recursion with an array or map to track the last value seen at each level.
What is the time complexity of Even Odd Tree?
The optimal solutions run in O(n) time because every node in the binary tree is visited exactly once. Each visit performs constant-time checks for parity and ordering. Space complexity is O(w) for BFS (tree width) or O(h) for DFS recursion depth.

Ready to solve this problem?

Practice Even Odd Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Inorder Traversal

Next

Unique Binary Search Trees II