Even Odd Tree — LeetCode 1609 Python Solution
MediumTreeBreadth-First SearchBinary Tree
- Problem
- #1609
- Pattern
- Tree Traversal
- Reading time
- 5 min
- Source
- leetcode.com
The problem
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).
Example
- Input
- root = [1,10,4,3,null,7,9,12,8,6,null,null,2]
- Output
- true
- Explanation
- The node values on each level are:
Python solution
Python
# 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:
even = 1
q = deque([root])
while q:
prev = 0 if even else inf
for _ in range(len(q)):
root = q.popleft()
if even and (root.val % 2 == 0 or prev >= root.val):
return False
if not even and (root.val % 2 == 1 or prev <= root.val):
return False
prev = root.val
if root.left:
q.append(root.left)
if root.right:
q.append(root.right)
even ^= 1
return TrueComplexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n), where n is the number of nodes in the binary tree auxiliary |
Pattern: Tree Traversal
Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 1609. Even Odd Tree is filed here because LeetCode tags it Tree and Binary Tree, which is the vocabulary this hub collects.
The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.
Related problems
LeetCode 102Binary Tree Level Order TraversalMediumLeetCode 103Binary Tree Zigzag Level Order TraversalMediumLeetCode 107Binary Tree Level Order Traversal IIMediumLeetCode 919Complete Binary Tree InserterMediumLeetCode 958Check Completeness of a Binary TreeMediumLeetCode 2471Minimum Number of Operations to Sort a Binary Tree by LevelMedium
Frequently asked questions
- How hard is LeetCode 1609. Even Odd Tree?
- LeetCode 1609. Even Odd Tree is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1609. Even Odd Tree?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 1609. Even Odd Tree?
- The Python solution on this page uses O(n), where n is the number of nodes in the binary tree auxiliary space.
- What topics does LeetCode 1609. Even Odd Tree cover?
- LeetCode 1609. Even Odd Tree is tagged Tree, Breadth-First Search and Binary Tree on LeetCode.