Even Odd Tree LeetCode solution in Python

1
from collections import deque
2

3
# Runtime:838ms 44.05% || Memory: 40.8mb 57.22%
4
# O(n) || O(h); where h is the height of the tree
5

6

7
class Solution:
8
    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
9
        if not root:
10
            return False
11

12
        level = 0
13
        evenOddLevel = {0: 1, 1: 0}
14
        queue = deque([root])
15

16
        while queue:
17
            prev = 0
18
            for _ in range(len(queue)):
19
                currNode = queue.popleft()
20
                comparison = {0: prev < currNode.val, 1: prev > currNode.val}
21
                if currNode.val % 2 != evenOddLevel[level % 2]:
22
                    return False
23
                else:
24
                    if prev != 0 and comparison[level % 2]:
25
                        prev = currNode.val
26
                    elif prev == 0:
27
                        prev = currNode.val
28
                    else:
29
                        return False
30

31
                if currNode.left:
32
                    queue.append(currNode.left)
33

34
                if currNode.right:
35
                    queue.append(currNode.right)
36

37
            level += 1
38

39
        return True