LeetCode 1609: Even Odd Tree Solution

Master LeetCode problem 1609 (Even Odd Tree), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1609. Even Odd Tree

Medium

Tree Breadth-First Search Binary Tree

Problem Explanation

Explanation

To determine if a binary tree is Even-Odd, we need to traverse the tree level by level and check if the values at each level satisfy the given conditions. If any level violates the conditions, then the tree is not Even-Odd. We can perform a BFS traversal of the tree while keeping track of the level and the values at each level.

Algorithm:

Perform a BFS traversal of the binary tree.
Keep track of the level (even or odd) and the expected value order for that level.
At each level, check if the values satisfy the conditions:
- For even levels, values should be odd and strictly increasing.
- For odd levels, values should be even and strictly decreasing.
If any level violates the conditions, return false.
If all levels satisfy the conditions, return true.

Time Complexity:

The time complexity of this algorithm is O(n), where n is the number of nodes in the binary tree. This is because we visit each node exactly once during the BFS traversal.

Space Complexity:

The space complexity of this algorithm is O(n), where n is the number of nodes in the binary tree. This is due to the space used by the queue for BFS traversal.

Solution Code

class Solution {
    public boolean isEvenOddTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int level = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            int prevValue = level % 2 == 0 ? Integer.MIN_VALUE : Integer.MAX_VALUE;

            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();

                if ((level % 2 == 0 && (node.val % 2 == 0 || node.val <= prevValue))
                        || (level % 2 == 1 && (node.val % 2 != 0 || node.val >= prevValue))) {
                    return false;
                }

                prevValue = node.val;

                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            level++;
        }

        return true;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1609 (Even Odd Tree)?

This page provides optimized solutions for LeetCode problem 1609 (Even Odd Tree) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1609 (Even Odd Tree)?

The time complexity for LeetCode 1609 (Even Odd Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1609 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1609 in Java, C++, or Python.

Back to LeetCode Solutions