Sponsored
Sponsored
This approach employs a breadth-first search (BFS) to traverse the binary tree level by level. We maintain a queue to keep track of the nodes at each level, examining their values to ensure compliance with the Even-Odd criteria:
Time Complexity: O(N), where N is the number of nodes, as each node is inspected once.
Space Complexity: O(M), where M is the maximum number of nodes at any level in the tree (width of the tree), due to the BFS queue.
1class TreeNode {
2 constructor(val, left = null, right = null) {
3 this.val = val;
4 this.left = left;
5 this.right = right;
6 }
7}
8
9function isEvenOddTree(root) {
10 if (!root) return false;
11
12 let queue = [root];
13 let level = 0;
14
15 while (queue.length > 0) {
16 let levelLength = queue.length;
17 let prev = null;
18
19 for (let i = 0; i < levelLength; i++) {
20 let node = queue.shift();
21
22 if (level % 2 === 0) {
23 if (node.val % 2 === 0 || (prev !== null && node.val <= prev)) {
24 return false;
25 }
26 } else {
27 if (node.val % 2 !== 0 || (prev !== null && node.val >= prev)) {
28 return false;
29 }
30 }
31
32 prev = node.val;
33
34 if (node.left) queue.push(node.left);
35 if (node.right) queue.push(node.right);
36 }
37
38 level++;
39 }
40
41 return true;
42}The JavaScript solution processes the tree similarly using a queue (BFS), checking odd/even conditions per level and comparing current node values to the previously processed node at the current level.
This approach applies a depth-first search (DFS) method, maintaining level information to confirm constraints. We use recursion to explore the tree, while an array stores the last value seen on each level to validate order constraints.
Time Complexity: O(N), with N being the number of nodes.
Space Complexity: O(H), where H is the height of the tree, accounting for recursion stack and the array storing last values at each level.
1import java.util.ArrayList;
2
3
The Java variant executes similar DFS logic, using an array to record last values per level. This aids in confirming if each level maintains the necessary order based on its index (even or odd).