1609. Even Odd Tree.md

1609. Even Odd Tree | C++ Solution | Breadth-First Search (BFS) | Depth-First Search (DFS) | Optimized Approach

Intuition

The problem is asking to check if a binary tree is an Even-Odd Tree. A binary tree is named Even-Odd if it meets the following conditions:

• The nodes at level 0 are all odd (i.e., their value is odd),
• The nodes at level 1 are all even (i.e., their value is even),
• Also, the values of the nodes at each level should be strictly decreasing for the level with an odd number and strictly increasing for the level with an even number.

Approach

1. Breadth-First Search (BFS): We can use BFS to traverse the tree level by level from left to right. We check the conditions at each level. If any condition fails, we return false. If we finish the traversal without any condition failing, we return true.

2. Depth-First Search (DFS): We can use DFS to traverse the tree and store the nodes at each level in a hash map. After the traversal, we check the conditions for each level in the hash map. If any condition fails, we return false. If we finish the check without any condition failing, we return true.

Complexity

• Breadth-First Search (BFS):

  • Time complexity: $O(n)$ because we traverse each node once.
  • Space complexity: $O(w)$ where $w$ is the maximum width of the tree, which is the maximum number of nodes at any level in the tree.

• Depth-First Search (DFS):

  • Time complexity: $O(n)$ because we traverse each node once.
  • Space complexity: $O(n)$ because we store all the nodes in the hash map.

Code

1. Breadth-First Search (BFS)

class Solution {
public:
    bool isEvenOddTree(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        int level = 0;
        while (!q.empty()) {
            int size = q.size();
            int prev = level % 2 == 0 ? INT_MIN : INT_MAX;
            while (size--) {
                TreeNode* node = q.front();
                q.pop();
                if (level % 2 == 0 && (node->val % 2 == 0 || node->val <= prev)) {
                    return false;
                }
                if (level % 2 != 0 && (node->val % 2 != 0 || node->val >= prev)) {
                    return false;
                }
                prev = node->val;
                if (node->left != NULL) {
                    q.push(node->left);
                }
                if (node->right != NULL) {
                    q.push(node->right);
                }
            }
            level++;
        }
        return true;
    }
};

2. Depth-First Search (DFS)

class Solution {
public:
    void help(TreeNode* root, unordered_map<int, vector<int>>& um, int h = 0) {
        if (root == NULL) return;

        um[h].push_back(root->val);

        help(root->left, um, h+1);
        help(root->right, um, h+1);
    }

    bool isEvenOddTree(TreeNode* root) {
        if (root->val % 2 == 0) return false;

        unordered_map<int, vector<int>> um;

        help(root, um);

        for (auto& i : um) {
            int n = i.second.size();
            if (i.first % 2 == 0) {
                for (int j = 0; j < n; j++) {
                    if (i.second[j] % 2 == 0) return false;
                    if (j+1 < n && i.second[j] >= i.second[j+1]) return false;
                }
            } else {
                for (int j = 0; j < n; j++) {
                    if (i.second[j] % 2 != 0) return false;
                    if (j+1 < n && i.second[j] <= i.second[j+1]) return false;
                }
            }
        }

        return true;
    }
};