Skip to content

1609. Even Odd Tree 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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