Even Odd Tree

Medium

Asked by:

85 views

Topics:

Trees

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).
For every odd-indexed level, all nodes at the level have even integer values in strictly decreasing order (from left to right).

Given the root of a binary tree, return true if the binary tree is Even-Odd, otherwise return false.

Example 1:

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:
Level 0: [1]
Level 1: [10,4]
Level 2: [3,7,9]
Level 3: [12,8,6,2]
Since levels 0 and 2 are all odd and increasing and levels 1 and 3 are all even and decreasing, the tree is Even-Odd.

Example 2:

Input: root = [5,4,2,3,3,7]
Output: false
Explanation: The node values on each level are:
Level 0: [5]
Level 1: [4,2]
Level 2: [3,3,7]
Node values in level 2 must be in strictly increasing order, so the tree is not Even-Odd.

Example 3:

Input: root = [5,9,1,3,5,7]
Output: false
Explanation: Node values in the level 1 should be even integers.

Constraints:

The number of nodes in the tree is in the range [1, 10⁵].
1 <= Node.val <= 10⁶

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the nodes in the tree? Can node values be negative or zero?
Can the tree be empty? What should I return in that case?
Are duplicate values allowed within a level? If so, what should happen?
Is the tree guaranteed to be a valid binary tree, or do I need to handle cases where a node has more than two children?
If a level is empty (has no nodes), should it still adhere to the even/odd property?

Brute Force Solution

Approach

The brute force method for the Even Odd Tree problem means we're going to check if the tree follows the rules, level by level. We will inspect every single node at each level to ensure it adheres to the even-odd characteristics required.

Here's how the algorithm would work step-by-step:

First, we need to visit all of the nodes in the tree, level by level, starting from the very top.
At each level, we will examine each number (node) individually to determine if it fits the level's rule. Even levels should only have odd numbers.
If a number at an even level is not odd, we immediately know the tree is not an Even-Odd Tree and we can stop checking.
Similarly, odd levels should only have even numbers. If we encounter an odd number at an odd level, the tree fails the Even-Odd test.
We also need to make sure the numbers increase on even levels as we move from left to right and decrease on odd levels from left to right.
So, for each level we will check if the current value is greater or smaller than the value from the node we saw before.
If after inspecting all the nodes we never find any violations, it means that all nodes in the tree obey all the necessary constraints for it to be classified as an Even-Odd Tree.

Code Implementation

from collections import deque

def is_even_odd_tree(root):
    if not root:
        return True

    queue = deque([root])
    level = 0

    while queue:
        level_size = len(queue)
        previous_value = None

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

            # Check even/odd property based on level
            if level % 2 == 0:
                if node.val % 2 == 0:
                    return False
                # Check increasing order for even levels
                if previous_value is not None and node.val <= previous_value:
                    return False
            else:
                if node.val % 2 != 0:
                    return False
                # Check decreasing order for odd levels
                if previous_value is not None and node.val >= previous_value:
                    return False

            previous_value = node.val

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

        level += 1

    return True

Big(O) Analysis

Time Complexity

O(n) – The algorithm traverses each node of the tree exactly once using a level-order traversal. For each node, a constant amount of work is performed: checking if its value is odd/even and comparing it with the previous node's value at that level. The input size is the number of nodes in the tree, denoted by n. Therefore, the time complexity is directly proportional to the number of nodes, resulting in O(n).

Space Complexity

O(W) – The primary auxiliary space usage comes from the level-by-level traversal, specifically the queue used to store nodes at each level. In the worst-case scenario, the queue could hold all nodes at the widest level of the tree. Therefore, the space complexity is determined by the maximum width (W) of the tree, where W is the maximum number of nodes at any single level. Thus, the space used by the queue is proportional to W. The other variables used (e.g., current level, previous value) take up constant space.

Optimal Solution

Approach

This problem requires us to check if a tree has alternating properties on each level. We use a level-by-level exploration to make sure each node meets the requirements of its level: even levels have odd values in increasing order, and odd levels have even values in decreasing order.

Here's how the algorithm would work step-by-step:

Start exploring the tree from the very top, considering it level zero.
Keep track of what level you are currently examining.
At each level, verify if all nodes at that level meet the specific criteria: odd values if the level is even and even values if the level is odd.
Also, check if the node values are in the right order. They should increase if the level is even, and decrease if the level is odd.
Move to the next level and repeat the process of verifying node values and their order.
If at any point you find a node that doesn't meet the level's criteria, immediately conclude that it's not an Even Odd Tree.
If you successfully explore all levels without finding any violations, then the tree *is* an Even Odd Tree.

Code Implementation

from collections import deque

def is_even_odd_tree(root):
    if not root:
        return True

    queue = deque([root])
    level = 0

    while queue:
        level_size = len(queue)
        previous_node_value = -1 if level % 2 == 0 else float('inf')

        for _ in range(level_size):
            current_node = queue.popleft()

            # Check odd/even property based on level.
            if level % 2 == 0:
                if current_node.val % 2 == 0:
                    return False
                # Check increasing order for even levels.
                if current_node.val <= previous_node_value:
                    return False
            else:
                if current_node.val % 2 != 0:
                    return False
                # Check decreasing order for odd levels.
                if current_node.val >= previous_node_value:
                    return False

            previous_node_value = current_node.val

            if current_node.left:
                queue.append(current_node.left)
            if current_node.right:
                queue.append(current_node.right)

        level += 1
    # If all nodes satisfy conditions, return True.
    return True

Big(O) Analysis

Time Complexity

O(n) – The algorithm performs a level-order traversal of the tree, visiting each node exactly once. The primary operation is checking the value and order of each node relative to its level and neighbors. Thus the work done is proportional to the number of nodes (n) in the tree. This results in O(n) time complexity.

Space Complexity

O(W) – The algorithm uses a level-order traversal, primarily employing a queue for storing nodes at each level. In the worst-case scenario, the queue will hold all nodes of the widest level in the tree. Therefore, the auxiliary space complexity is determined by the maximum width (W) of the tree, where W is the maximum number of nodes at any level. This queue is the only auxiliary space used in the algorithm. Hence, the space complexity is O(W).

Edge Cases

Case	How to Handle
Null root node	Return true immediately since an empty tree technically satisfies the level conditions.
Single node tree with root value violating level constraints	Check root node value parity against level parity (level 0 should be odd) and return false if violated.
Skewed tree with very deep levels	Ensure BFS implementation avoids excessive memory usage and stack overflow errors.
Tree with all nodes having same value.	The level-wise checks for strictly increasing/decreasing values will detect the violation and return false.
Large integer values causing potential overflow in comparison.	Use appropriate data types (e.g., long) if node values can be extremely large to prevent overflow during comparisons.
Level with only one node	Ensure increasing/decreasing checks don't cause errors; single node automatically satisfies the condition.
Level with non-consecutive even or odd numbers (e.g., 1, 5, 9 or 2, 6, 10)	The increasing/decreasing check correctly handles non-consecutive sequences if they are strictly increasing/decreasing.
Tree with negative node values.	The parity check and increasing/decreasing checks should work correctly with negative numbers.

Null root node

How to Handle:

Return true immediately since an empty tree technically satisfies the level conditions.

Single node tree with root value violating level constraints

How to Handle:

Check root node value parity against level parity (level 0 should be odd) and return false if violated.

Skewed tree with very deep levels

How to Handle:

Ensure BFS implementation avoids excessive memory usage and stack overflow errors.

Tree with all nodes having same value.

How to Handle:

The level-wise checks for strictly increasing/decreasing values will detect the violation and return false.

Large integer values causing potential overflow in comparison.

How to Handle:

Use appropriate data types (e.g., long) if node values can be extremely large to prevent overflow during comparisons.

Level with only one node

How to Handle:

Ensure increasing/decreasing checks don't cause errors; single node automatically satisfies the condition.

Level with non-consecutive even or odd numbers (e.g., 1, 5, 9 or 2, 6, 10)

How to Handle:

The increasing/decreasing check correctly handles non-consecutive sequences if they are strictly increasing/decreasing.

Tree with negative node values.

How to Handle:

The parity check and increasing/decreasing checks should work correctly with negative numbers.