Even odd tree

Tree Breadth-First Search Binary Tree

67.0% acceptance

Feb 27, 2026

1880

102

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
  pub fn is_even_odd_tree(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
    use std::collections::VecDeque;
    let mut queue = VecDeque::new();
    if let Some(r) = root { queue.push_back(r); }
    let mut level = 0i32;
    while !queue.is_empty() {
      let size = queue.len();
      let mut prev: Option<i32> = None;
      for _ in 0..size {
        let node = queue.pop_front().unwrap();
        let val = node.borrow().val;
        if level % 2 == 0 {
          // even level: must be odd and strictly increasing
          if val % 2 == 0 { return false; }
          if let Some(p) = prev { if val <= p { return false; } }
        } else {
          // odd level: must be even and strictly decreasing
          if val % 2 == 1 { return false; }
          if let Some(p) = prev { if val >= p { return false; } }
        }
        prev = Some(val);
        let left = node.borrow().left.clone();
        let right = node.borrow().right.clone();
        if let Some(l) = left { queue.push_back(l); }
        if let Some(r) = right { queue.push_back(r); }
      }
      level += 1;
    }
    true
  }
}