Even Odd Tree - LeetCode Daily Challenge

Problem Statement

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.

Try here before watching the video.

Video Solution

Java Code

class Solution {
    public boolean isEvenOddTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        boolean isLevelEven = true;

        while(!queue.isEmpty()) {
            int levelSize = queue.size();
            int previousValue = Integer.MIN_VALUE;
            if(!isLevelEven) {
                previousValue = Integer.MAX_VALUE;
            }
            for(int i = 0; i < levelSize; i++) {
                TreeNode curr = queue.poll();
                
                if(isLevelEven && (curr.val % 2 == 0 || curr.val <= previousValue)) {
                    return false;
                }

                if(!isLevelEven && (curr.val % 2 == 1 || curr.val >= previousValue)) {
                    return false;
                }

                previousValue = curr.val;

                if(curr.left != null) {
                    queue.add(curr.left);
                }
                if(curr.right != null) {
                    queue.add(curr.right);
                }
            }
            isLevelEven = !isLevelEven;
        }

        return true;
    }
}

C++ Code

class Solution {
public:
    bool isEvenOddTree(TreeNode* root) {
        if (!root) return true;
        
        queue<TreeNode*> queue;
        queue.push(root);
        bool isLevelEven = true;

        while (!queue.empty()) {
            int levelSize = queue.size();
            int previousValue = (isLevelEven) ? INT_MIN : INT_MAX;
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode* curr = queue.front();
                queue.pop();

                if (isLevelEven && (curr->val % 2 == 0 || curr->val <= previousValue))
                    return false;

                if (!isLevelEven && (curr->val % 2 == 1 || curr->val >= previousValue))
                    return false;

                previousValue = curr->val;

                if (curr->left)
                    queue.push(curr->left);
                if (curr->right)
                    queue.push(curr->right);
            }
            isLevelEven = !isLevelEven;
        }

        return true;
    }
};

Python Code

class Solution:
    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        
        queue = deque([root])
        isLevelEven = True

        while queue:
            levelSize = len(queue)
            previousValue = float('-inf') if isLevelEven else float('inf')
            
            for _ in range(levelSize):
                curr = queue.popleft()
                
                if (isLevelEven and (curr.val % 2 == 0 or curr.val <= previousValue)):
                    return False

                if(not isLevelEven and (curr.val % 2 == 1 or curr.val >= previousValue)):
                    return False

                previousValue = curr.val

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

            isLevelEven = not isLevelEven

        return True

Javascript Code

var isEvenOddTree = function(root) {
    
    let queue = [root];
    let isLevelEven = true;

    while (queue.length > 0) {
        let levelSize = queue.length;
        let previousValue = isLevelEven ? -Infinity : Infinity;

        for (let i = 0; i < levelSize; i++) {
            let curr = queue.shift();

            if (isLevelEven && (curr.val % 2 === 0 || curr.val <= previousValue)) {
                return false;
            }
            
            if(!isLevelEven && (curr.val % 2 === 1 || curr.val >= previousValue)) {
                return false;
            }

            previousValue = curr.val;

            if (curr.left) queue.push(curr.left);
            if (curr.right) queue.push(curr.right);
        }

        isLevelEven = !isLevelEven;
    }

    return true;
};

Go Code

func isEvenOddTree(root *TreeNode) bool {
    
    queue := []*TreeNode{root}
    isLevelEven := true

    for len(queue) > 0 {
        levelSize := len(queue)
        previousValue := 0
        if isLevelEven {
            previousValue = math.MinInt64
        } else {
            previousValue = math.MaxInt64
        }

        for i := 0; i < levelSize; i++ {
            curr := queue[0]
            queue = queue[1:]

            if (isLevelEven && (curr.Val%2 == 0 || curr.Val <= previousValue)) {
                return false
            }
               
            if (!isLevelEven && (curr.Val%2 == 1 || curr.Val >= previousValue)) {
                return false
            }

            previousValue = curr.Val

            if curr.Left != nil {
                queue = append(queue, curr.Left)
            }
            if curr.Right != nil {
                queue = append(queue, curr.Right)
            }
        }

        isLevelEven = !isLevelEven
    }

    return true
}

Complexity Analysis

Time Complexity: O(N), as we are iterating over all the nodes.
Space Complexity: O(N), as we are storing almost all the nodes in the queue at a time.