How to Solve Even Odd Tree

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 setting 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 dependent 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 absolute difference.