Even Odd Tree - Leetcode Solution

Problem Description:

A binary tree is named Even-Odd if it meets the following conditions:

• The root of the tree is at level 0, with odd value.
• For every even level, all nodes at that level have odd values in strictly increasing order (from left to right).
• For every odd level, all nodes at that level have even values in strictly decreasing order (from left to right).

The binary tree may have any number of nodes, and there may be different ways to construct Still, a binary tree is Even-Odd if it satisfies these conditions.

Write a function that determines whether a binary tree is Even-Odd or not.

Solution:

We need to traverse the Binary Tree in a level-order fashion to check the Even-Odd properties. We can use a queue to store the nodes at each level, and we can also keep track of the previous node's value and level to check if the properties are satisfied.

Algorithm:

1. Initialize a queue with the root node of the binary tree and a level variable with 0.
2. While the queue is not empty, perform the following steps: a. Initialize a prev variable with None, and a flag variable that will be used to determine if all nodes at this level satisfy the Even-Odd properties. b. Get the size of the queue and iterate that many times to process all nodes at this level. i. Dequeue a node from the queue. ii. Check if the node value satisfies the Even-Odd properties, and update the flag variable accordingly. iii. If the prev variable is not None, check if the Even-Odd properties are satisfied for the current node and the previous node. If not, return False. iv. Set the prev variable to the current node. v. Enqueue the left and right children of the current node to the queue if they exist. c. Increment the level variable by 1. d. If the flag variable is False, return False since not all nodes at this level satisfy the Even-Odd properties.
3. If all levels satisfy the Even-Odd properties, return True.

Code in Python:

class Solution:
    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        
        queue = [root]
        level = 0
        
        while queue:
            prev = None
            flag = True
            size = len(queue)
            
            for i in range(size):
                node = queue.pop(0)
                
                if level % 2 == 0:
                    if node.val % 2 == 0 or (prev and prev.val >= node.val):
                        flag = False
                        break
                else:
                    if node.val % 2 != 0 or (prev and prev.val <= node.val):
                        flag = False
                        break
                
                prev = node
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            if not flag:
                return False
            
            level += 1
        
        return True

Time Complexity:

The time complexity of the algorithm is O(n), where n represents the number of nodes in the Binary Tree. We are processing each node exactly once during the level-order traversal.

Space Complexity:

The space complexity of the algorithm is O(d), where d represents the maximum depth of the Binary Tree. We are maintaining a queue that may contain all the nodes at the deepest level of the tree. However, the worst-case scenario is that the Binary Tree is a complete Binary Tree, and the number of nodes at the deepest level is at most half of the total nodes. Thus, the space complexity is O(n/2) or O(n) for complete Binary Trees.

1