Even Odd Tree

Medium · Graphs · Explanation and code example

Iterative DFS

How it works

This approach mimics recursive DFS using an explicit stack, which can help avoid stack overflow for very deep trees. We store (node, level) pairs on the stack and process nodes in a similar order to recursive DFS.

The same levels array tracks the last seen value at each depth. By pushing the right child before the left child, we ensure left-to-right traversal order when popping.

Steps

  1. Initialize a stack with (root, 0) and a levels array.
  2. While the stack is not empty:
    • Pop a (node, level) pair.
    • Check the parity constraint for the node's value. Return false if violated.
    • If this is the first node at this level, append the value to levels.
    • Otherwise, check the ordering constraint and update levels[level]. Return false if violated.
    • Push the right child (if exists) then the left child (if exists) with level + 1.
  3. If processing completes without violations, return true.

Complexity

  • Time complexity: O(n)
  • Space complexity: O(n)

Things to watch for

Confusing Level Index with Value Parity

Even-indexed levels (0, 2, 4, ...) must have odd VALUES, while odd-indexed levels (1, 3, 5, ...) must have even VALUES. It is easy to mix these up and check if values match the level parity, which is the opposite of what the problem requires. Remember: level parity and value parity must be different.

Using Non-Strict Inequality for Ordering

The problem requires STRICTLY increasing order on even levels and STRICTLY decreasing order on odd levels. Using <= instead of < for increasing, or >= instead of > for decreasing, will incorrectly accept trees where adjacent nodes have equal values. Equal values at the same level should cause the function to return false.

Forgetting to Reset Previous Value Between Levels

When processing each level, the prev tracking variable must be reset to an appropriate initial value (negative infinity for even levels, positive infinity for odd levels). If you forget to reset it or initialize it incorrectly, comparisons with the first node of each level will fail, causing valid trees to be rejected or invalid trees to be accepted.

Python code example

from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isEvenOddTree(self, root: Optional[TreeNode]) -> bool:
        stack = [(root, 0)]
        levels = []

        while stack:
            node, level = stack.pop()

            even = level % 2 == 0
            if ((even and node.val % 2 == 0) or
                (not even and node.val % 2 == 1)
            ):
                return False

            if len(levels) == level:
                levels.append(node.val)
            else:
                if ((even and node.val <= levels[level]) or
                    (not even and node.val >= levels[level])
                ):
                    return False
                levels[level] = node.val

            if node.right:
                stack.append((node.right, level + 1))
            if node.left:
                stack.append((node.left, level + 1))

        return True

C++ code example

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isEvenOddTree(TreeNode* root) {
        stack<pair<TreeNode*, int>> stack;
        stack.push({root, 0});
        vector<int> levels;

        while (!stack.empty()) {
            auto [node, level] = stack.top();
            stack.pop();

            bool even = level % 2 == 0;
            if ((even && node->val % 2 == 0) ||
                (!even && node->val % 2 == 1))
                return false;

            if (levels.size() == level) {
                levels.push_back(node->val);
            } else {
                if ((even && node->val <= levels[level]) ||
                    (!even && node->val >= levels[level]))
                    return false;
                levels[level] = node->val;
            }

            if (node->right) stack.push({node->right, level + 1});
            if (node->left) stack.push({node->left, level + 1});
        }

        return true;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations