LeetCode Entry

1609. Even Odd Tree

29.02.2024 medium 2024 kotlin rust

Binary tree levels are odd increasing and even decreasing.

1609. Even Odd Tree medium blog post substack youtube image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/523

Problem TLDR

Binary tree levels are odd increasing and even decreasing.

Intuition

Just use level-order BFS traversal.

Approach

Let’s try to make code shorter by simplifying the if condition.

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\), the last level of the Binary Tree is almost n/2 nodes.

Code


  fun isEvenOddTree(root: TreeNode?) = ArrayDeque<TreeNode>().run {
    root?.let { add(it) }
    var inc = true
    while (size > 0) {
      var prev = 0
      repeat(size) { removeFirst().run {
        if (`val` % 2 > 0 != inc || `val` == prev
         || `val` < prev == inc && prev > 0) return false
        left?.let { add(it) }; right?.let { add(it) }
        prev = `val`
      }}
      inc = !inc
    }; true
  }



  pub fn is_even_odd_tree(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
    let mut q = VecDeque::new();
    if let Some(n) = root { q.push_back(n) }
    let mut inc = true;
    while !q.is_empty() {
      let mut prev = 0;
      for _ in 0..q.len() { if let Some(n) = q.pop_front() {
        let n = n.borrow(); let v = n.val;
        if (v % 2 > 0) != inc || v == prev
        || (v < prev) == inc && prev > 0 { return false }
        if let Some(l) = n.left.clone() { q.push_back(l) }
        if let Some(r) = n.right.clone() { q.push_back(r) }
        prev = v
      }}
      inc = !inc
    } true
  }