Even Odd Tree - Leetcode 1609 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
4:54 - Coding Explanation

leetcode 1609

#neetcode #leetcode #python

[randomBoulevards]

You taught me coding Neetcode. Please keep posting such videos !!

Solved the above this same morning 😇😇, All credits to you :

def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
q, level = collections.deque([]), 1
q.extend((root, None))
while q:
node = q.popleft()
if not node:
if not q:
break
level += 1
q.append(None)
continue
if level % 2 == 0:
if node.val % 2 == 1 or (q[0] and node.val <= q[0].val):
return False
else:
if node.val % 2 == 0 or (q[0] and node.val >= q[0].val):
return False
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return True

[kziad]

Starting my leetcode journey today. Thanks for your help!

[maheshm]

This is the first time i am able to solve something of my own with out seeing the solution Video. All thanks to you @Neetcode

[mudyeet_]

Gotta go through some BFS videos first, the code is so simple yet does so much

[zaki_]

This problem took longer than it should have because of all the conditions 🤦🏻‍♂

[DeathSugar]

Why didn't it cry about indentation at 18 and 20?

[thiagosdev]

This is mine:

class Solution:
def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
if root is None: return False

queue = deque()
queue.append(root)

levelOdd = True

while queue:
levelOdd = not levelOdd # flip the level
prev = None

for _ in range(len(queue)):
node = queue.popleft()

if levelOdd:
if node.val % 2 != 0: return False # if curr level is odd, then all nodes should be even not odd
if prev and prev <= node.val: return False
else: # even
if node.val % 2 == 0: return False
if prev and prev >= node.val: return False

prev = node.val

## add children
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)

return True

[axaide]

If you're curious, here is my DFS solution using in-order traversal. Overall I think my solution is worse since there will be a lot of overhead for function recursion in large trees.

class Solution:
def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
d = defaultdict(int)
def traverse(node, level):
if node is None:
return True
if not traverse(node.left, level+1):
return False
#even level, odd value, vice versa
if node.val % 2 != level%2:
if level%2 == 0:
if (d[level] == 0 or d[level] < node.val):
d[level] = node.val
else:
return False
else:
if (d[level] == 0 or d[level] > node.val):
d[level] = node.val
else:
return False
else:
return False

if not traverse(node.right, level+1):
return False
return True

return traverse(root, 0)