medium Even Odd Tree

Problem Statement

Given a binary tree, return true if it is an Even-Odd tree. Otherwise, return false.

The Even-odd tree must follow below two rules:

1. At every even-indexed level (starting from 0), all node values must be odd and arranged in strictly increasing order from left to right.
2. At every odd-indexed level, all node values must be even and arranged in strictly decreasing order from left to right.

Examples

Example 1

• Input:

    1
   / \
  10  4
 / \
3   7

• Expected Output: true
• Justification: The tree follows both conditions for each odd and even level. So, it is an odd-even tree.

Example 2

Input:

    5
   / \
  9   3
 /     \
12      8

• Expected Output: false
• Justification: Level 1 has Odd values 9 and 3 in decreasing order, but it should have even values. So, the tree is not an odd-even tree.

Example 3

• Input:

    7
   / \
  10  2
 / \
12  8

• Expected Output: false
• Justification: At level 2 (even-indexed), the values are 12 and 8, which are even, but they should have odd values. So, the tree is not an odd-even tree.

Constraints:

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

Solution

To solve this problem, we can perform a level-order traversal (BFS) of the binary tree. During this traversal, we will keep track of the current level index to check whether it is even or odd. For each level, we will store the node values and verify the required conditions:

• If the level is even, the values should be odd and in strictly increasing order.
• If the level is odd, the values should be even and in strictly decreasing order.

This approach is efficient because it allows us to traverse each node once and check the conditions in a single pass. By maintaining a queue for BFS and lists for each level's values, we can ensure that all conditions are checked accurately.

Step-by-step Algorithm

1. Initialize a queue for level-order traversal and add the root node to it.
2. Initialize a variable level to 0 to keep track of the current level.
3. While the queue is not empty:
   • Determine the number of nodes at the current level (size).
   • Create an empty list (values) to store the values of the nodes at the current level.
   • For each node in the current level:
     • Remove the node from the queue.
     • Add its value to the values list.
     • If the node has a left child, add it to the queue.
     • If the node has a right child, add it to the queue.
   • Check the values collected at the current level:
     • If the level is even:
       • Ensure all values are odd and strictly increasing.
     • If the level is odd:
       • Ensure all values are even and strictly decreasing.
   • If the values do not meet the required conditions, return false.
   • Increment the level by 1.
4. Return true if all levels meet the required conditions.

Algorithm Walkthrough

Input Tree:

    1
   / \
  10  4
 / \
3   7

Steps:

1. Initialization:

   • Queue: [1]
   • Level: 0

2. Level 0:

   • Size: 1
   • Values: []
   • Process node 1:
     • Queue: []
     • Values: [1]
     • Add left child (10) to the queue
     • Add right child (4) to the queue
   • Check values for even level:
     • Values: [1] (all odd and strictly increasing)
   • Increment level: 1

3. Level 1:

   • Size: 2
   • Values: []
   • Process node 10:
     • Queue: [4]
     • Values: [10]
     • Add left child (3) to the queue
     • Add right child (7) to the queue
   • Process node 4:
     • Queue: [3, 7]
     • Values: [10, 4]
   • Check values for odd level:
     • Values: [10, 4] (all even and strictly decreasing)
   • Increment level: 2

4. Level 2:

   • Size: 2
   • Values: []
   • Process node 3:
     • Queue: [7]
     • Values: [3]
   • Process node 7:
     • Queue: []
     • Values: [3, 7]
   • Check values for even level:
     • Values: [3, 7] (all odd and strictly increasing)
   • Increment level: 3

5. Completion:

   • Queue is empty, all levels meet the required conditions.
   • Return true.

Code

import java.util.*;

// class TreeNode {
//     int val;
//     TreeNode left, right;
//     TreeNode(int val) {
//         this.val = val;
//     }
// }

class Solution {

  public boolean isEvenOddTree(TreeNode root) {
    if (root == null) return true; // Check if the tree is empty

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root); // Initialize the queue with the root node
    int level = 0; // Start with level 0

    while (!queue.isEmpty()) {
      int size = queue.size();
      List<Integer> values = new ArrayList<>(); // List to store node values at current level

      for (int i = 0; i < size; i++) {
        TreeNode node = queue.poll(); // Get the next node in the queue
        values.add(node.val); // Add its value to the list

        if (node.left != null) queue.offer(node.left); // Add left child to the queue if it exists
        if (node.right != null) queue.offer(node.right); // Add right child to the queue if it exists
      }

      // Check values for the current level
      if (level % 2 == 0) {
        for (int i = 0; i < values.size(); i++) {
          if (
            values.get(i) % 2 == 0 ||
            (i > 0 && values.get(i) <= values.get(i - 1))
          ) {
            return false; // Even level: values must be odd and strictly increasing
          }
        }
      } else {
        for (int i = 0; i < values.size(); i++) {
          if (
            values.get(i) % 2 != 0 ||
            (i > 0 && values.get(i) >= values.get(i - 1))
          ) {
            return false; // Odd level: values must be even and strictly decreasing
          }
        }
      }
      level++; // Move to the next level
    }
    return true; // If all levels satisfy the conditions, return true
  }

  public static void main(String[] args) {
    Solution sol = new Solution();

    // Example 1
    TreeNode root1 = new TreeNode(1);
    root1.left = new TreeNode(10);
    root1.right = new TreeNode(4);
    root1.left.left = new TreeNode(3);
    root1.left.right = new TreeNode(7);
    System.out.println(sol.isEvenOddTree(root1)); // Output: true

    // Example 2
    TreeNode root2 = new TreeNode(5);
    root2.left = new TreeNode(9);
    root2.right = new TreeNode(3);
    root2.left.left = new TreeNode(12);
    root2.right.right = new TreeNode(8);
    System.out.println(sol.isEvenOddTree(root2)); // Output: false

    // Example 3
    TreeNode root3 = new TreeNode(7);
    root3.left = new TreeNode(10);
    root3.right = new TreeNode(2);
    root3.left.left = new TreeNode(12);
    root3.left.right = new TreeNode(8);
    System.out.println(sol.isEvenOddTree(root3)); // Output: false
  }
}

Complexity Analysis

Time Complexity

The algorithm performs a level-order traversal of the binary tree, which means it visits each node exactly once. Therefore, the time complexity is , where n is the number of nodes in the tree.

Space Complexity

The space complexity is determined by the maximum number of nodes at any level in the binary tree. In the worst case, this can be in a perfectly balanced tree. The space required for the queue in the level-order traversal is proportional to the number of nodes at the deepest level, which is in the worst case, simplifying to .