1609. Even Odd Tree LeetCode Solution

Last updated: February 24, 2025

In this guide, you will get 1609. Even Odd Tree LeetCode Solution with the best time and space complexity. The solution to Even Odd Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Even Odd Tree solution in C++
Even Odd Tree solution in Java
Even Odd Tree solution in Python
Additional Resources

1609. Even Odd Tree LeetCode Solution image

Problem Statement of Even Odd Tree

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

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

1609. Even Odd Tree LeetCode Solution in C++

class Solution {
 public:
  bool isEvenOddTree(TreeNode* root) {
    queue<TreeNode*> q{{root}};
    bool isEven = true;

    for (; !q.empty(); isEven = !isEven) {
      int prevVal = isEven ? INT_MIN : INT_MAX;
      for (int sz = q.size(); sz > 0; --sz) {
        TreeNode* node = q.front();
        q.pop();
        if (isEven && (node->val % 2 == 0 || node->val <= prevVal))
          return false;  // invalid case on even level
        if (!isEven && (node->val % 2 == 1 || node->val >= prevVal))
          return false;  // invalid case on odd level
        prevVal = node->val;
        if (node->left != nullptr)
          q.push(node->left);
        if (node->right != nullptr)
          q.push(node->right);
      }
    }

    return true;
  }
};
/* code provided by PROGIEZ */

1609. Even Odd Tree LeetCode Solution in Java

class Solution {
  public boolean isEvenOddTree(TreeNode root) {
    Queue<TreeNode> q = new LinkedList<>(Arrays.asList(root));
    boolean isEven = true;

    for (; !q.isEmpty(); isEven = !isEven) {
      int prevVal = isEven ? Integer.MIN_VALUE : Integer.MAX_VALUE;
      for (int sz = q.size(); sz > 0; --sz) {
        TreeNode node = q.poll();
        if (isEven && (node.val % 2 == 0 || node.val <= prevVal))
          return false; // invalid case on even level
        if (!isEven && (node.val % 2 == 1 || node.val >= prevVal))
          return false; // invalid case on odd level
        prevVal = node.val;
        if (node.left != null)
          q.offer(node.left);
        if (node.right != null)
          q.offer(node.right);
      }
    }

    return true;
  }
}
// code provided by PROGIEZ

1609. Even Odd Tree LeetCode Solution in Python

class Solution:
  def isEvenOddTree(self, root: TreeNode | None) -> bool:
    q = collections.deque([root])
    isEven = True

    while q:
      prevVal = -math.inf if isEven else math.inf
      for _ in range(sz):
        node = q.popleft()
        if isEven and (node.val % 2 == 0 or node.val <= prevVal):
          return False  # invalid case on even level
        if not isEven and (node.val % 2 == 1 or node.val >= prevVal):
          return False  # invalid case on odd level
        prevVal = node.val
        if node.left:
          q.append(node.left)
        if node.right:
          q.append(node.right)
      isEven = not isEven

    return True
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents