MEDIUM
DATA STRUCTURES AND ALGORITHMS

# How to Solve Even Odd Tree

Written By ## Even Odd Tree Introduction

The Even Odd Tree problem asks us to return true if each even level of the tree's values are increasing while all odd levels are decreasing otherwise return false. To solve this we can traverse the binary tree level by level, pass the root node into a queue and process each node in the queue during each iteration, we can check if the values of the nodes at the current level meet the requirements based on their level index.

## Even Odd Tree Problem

Given a tree, verify that on even levels, all values in the level are strictly increasing and even. On odd levels, verify all values in the level are strictly decreasing and odd.

### Example Inputs and Outputs

#### Example 1

Input: root = [1,10,4,3,null,7,9,12,8,6,null,null,2]
Output: True

#### Example 2

Input: root = [5,4,2,3,3,7]
Output: False

## Even Odd Tree Solutions

To solve this problem, we can traverse the binary tree level by level and check if the nodes satisfy the conditions. We start at the root node and process each level one by one, making sure that the values meet the criteria set out by the problem.

We start by settting up a queue or a similar data structure (can use deque) to hold the nodes of each level. We add the root node to the queue and then proceed to process each node in the queue. During each iteration, we can check if the values of the nodes at the current level meet the requirements based on their level index. If any node invalidates the conditions in the problem, we then know that the binary tree is not an "Even-Odd" binary tree and return False.

``````class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

def isEvenOddTree(root):
if not root:
return False

queue = [root]
level_index = 0

while queue:
level_size = len(queue)
prev_val = None
next_level = []

for _ in range(level_size):
node = queue.pop(0)
val = node.val

if (level_index % 2 == 0 and (val % 2 != 1 or (prev_val is not None and val <= prev_val))) or \
(level_index % 2 != 0 and (val % 2 != 0 or (prev_val is not None and val >= prev_val))):
return False

prev_val = val

if node.left:
next_level.append(node.left)
if node.right:
next_level.append(node.right)

queue = next_level
level_index += 1

return True

# Driver code to test the function
# We'll create the following tree:
#     1
#    / \
#   10  4
#  /  \    \
#  3   7   9
root = TreeNode(1)
root.left = TreeNode(10)
root.right = TreeNode(4)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.right = TreeNode(9)

print(isEvenOddTree(root))  # Output: True

# Our second tree:
#     5
#    /    \
#   4     2
#  /  \     /
#  3   3 7
root2 = TreeNode(5)
root2.left = TreeNode(4)
root2.right = TreeNode(2)
root2.left.left = TreeNode(3)
root2.left.right = TreeNode(3)
root2.right.left = TreeNode(7)

print(isEvenOddTree(root2))  # Output: False``````

#### Time/Space Complexity Analysis

• Time Complexity: O(N), where n is the total number of nodes in the binary tree as we visit each node once.
• Space Complexity: O(m), where m represents the maximum number of nodes at any level in the binary tree.

Note:

In this solution, the space is not dependant on the height of the tree as would be the case in a recursive solution

It is possible to achieve O(1) space complexity by checking parent and child absolutely difference