How to Solve Even Odd Tree

Written By
Adam Bhula

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:
            if 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.


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

About is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.

We know exactly what to do and say to get the company, title, and salary you want.

Interview prep and job hunting are chaos and pain. We can help. Really.