_1609. Even Odd Tree.md

1609. Even Odd Tree

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 05, 2024

Last updated : July 05, 2024

---

Related Topics : Tree, Breadth-First Search, Binary Tree

Acceptance Rate : 66.46 %

---

Version 1:

Stores each value in a defaultdict of stacks to compare a current value with the last in its current depth.

Version 2:

Uses a single stack which achieves a max len() of the height of the graph. Since we're conducting a DFS traversal, we can compare the values according to the preorder traversal, and thus don't have to store any value except for the value immediately preceding it left to right on its current level.

We can also simply ignore this comparison if it's the first of a given depth.

---

Solutions

• m1609 v1 levelOrderStacks.py
• m1609 v2 singleValStorage.py

Python

m1609 v1 levelOrderStacks.py

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
        vals = defaultdict(list)

        def dfs(curr: Optional[TreeNode], lvl: int = 0) -> bool :
            if not curr :
                return True
            if curr.val % 2 == lvl % 2 :
                return False
            if lvl in vals and ((lvl % 2 == 0 and vals[lvl][-1] >= curr.val) or \
                                (lvl % 2 == 1 and vals[lvl][-1] <= curr.val)) :
                return False
            
            vals[lvl].append(curr.val)
            
            lvl += 1
            return dfs(curr.left, lvl) and dfs(curr.right, lvl)
            
        return dfs(root)

m1609 v2 singleValStorage.py

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
        vals = []

        def dfs(curr: Optional[TreeNode], lvl: int = 0) -> bool :
            if not curr :
                return True

            if curr.val % 2 == lvl % 2 :
                return False
            
            if len(vals) <= lvl :
                vals.append(curr.val)
            elif vals[lvl] and ((lvl % 2 == 0 and vals[lvl] >= curr.val) or \
                                (lvl % 2 == 1 and vals[lvl] <= curr.val)) :
                return False
            else :
                vals[lvl] = curr.val
            
            lvl += 1
            return dfs(curr.left, lvl) and dfs(curr.right, lvl)
            
        return dfs(root)