Even Odd Tree solution and explanation

from collections import deque

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: TreeNode) -> bool:
        if not root:
            return False

        queue = deque([root])
        level = 0

        while queue:
            level_length = len(queue)
            prev = None

            for _ in range(level_length):
                node = queue.popleft()

                # Check current node value with constraints
                if level % 2 == 0:
                    if node.val % 2 == 0 or (prev is not None and node.val <= prev):
                        return False
                else:
                    if node.val % 2 != 0 or (prev is not None and node.val >= prev):
                        return False

                prev = node.val

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

            level += 1

        return True

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function isEvenOddTree(root) {
    if (!root) return false;

    let queue = [root];
    let level = 0;

    while (queue.length > 0) {
        let levelLength = queue.length;
        let prev = null;

        for (let i = 0; i < levelLength; i++) {
            let node = queue.shift();

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

            prev = node.val;

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

        level++;
    }

    return true;
}

import java.util.ArrayList;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public boolean isValid(TreeNode node, int level, ArrayList<Integer> lastVals) {
        if (node == null) return true;

        if (lastVals.size() <= level) {
            lastVals.add(level % 2 == 0 ? Integer.MIN_VALUE : Integer.MAX_VALUE);
        }

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

        lastVals.set(level, node.val);

        return isValid(node.left, level + 1, lastVals) && isValid(node.right, level + 1, lastVals);
    }

    public boolean isEvenOddTree(TreeNode root) {
        ArrayList<Integer> lastVals = new ArrayList<>();
        return isValid(root, 0, lastVals);
    }
}

#include <vector>
#include <algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    bool isValid(TreeNode* node, int level, vector<int>& lastVals) {
        if (!node) return true;

        if (lastVals.size() <= level) {
            lastVals.push_back(level % 2 == 0 ? INT_MIN : INT_MAX);
        }

        if ((level % 2 == 0 && (node->val % 2 == 0 || node->val <= lastVals[level])) ||
            (level % 2 == 1 && (node->val % 2 == 1 || node->val >= lastVals[level]))) {
            return false;
        }

        lastVals[level] = node->val;

        return isValid(node->left, level + 1, lastVals) && isValid(node->right, level + 1, lastVals);
    }

    bool isEvenOddTree(TreeNode* root) {
        vector<int> lastVals;
        return isValid(root, 0, lastVals);
    }
};

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isEvenOddTree(root *TreeNode) bool {
	even := true
	q := []*TreeNode{root}
	for len(q) > 0 {
		var prev int = 1e7
		if even {
			prev = 0
		}
		for n := len(q); n > 0; n-- {
			root = q[0]
			q = q[1:]
			if even && (root.Val%2 == 0 || prev >= root.Val) {
				return false
			}
			if !even && (root.Val%2 == 1 || prev <= root.Val) {
				return false
			}
			prev = root.Val
			if root.Left != nil {
				q = append(q, root.Left)
			}
			if root.Right != nil {
				q = append(q, root.Right)
			}
		}
		even = !even
	}
	return true
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isEvenOddTree(root *TreeNode) bool {
	d := map[int]int{}
	var dfs func(*TreeNode, int) bool
	dfs = func(root *TreeNode, i int) bool {
		if root == nil {
			return true
		}
		even := i%2 == 0
		prev, ok := d[i]
		if !ok {
			if even {
				prev = 0
			} else {
				prev = 10000000
			}
		}
		if even && (root.Val%2 == 0 || prev >= root.Val) {
			return false
		}
		if !even && (root.Val%2 == 1 || prev <= root.Val) {
			return false
		}
		d[i] = root.Val
		return dfs(root.Left, i+1) && dfs(root.Right, i+1)
	}
	return dfs(root, 0)
}