1609. Even Odd Tree
Problem Description
The problem provides a binary tree and introduces a special condition called Even-Odd. A binary tree meets the Even-Odd condition if:
- The root node is at level 0, its children are at level 1, their children at level 2, and so on.
- Nodes at levels with an even index (like 0, 2, 4, ...) must have odd integer values, and these values must be in strictly increasing order from left to right.
- Nodes at levels with an odd index (like 1, 3, 5, ...) must have even integer values, and these values must be in strictly decreasing order from left to right.
The goal is to write a function that takes the root node of a binary tree as an input and returns true
if the tree satisfies the Even-Odd condition; otherwise, it should return false
.
Flowchart Walkthrough
To determine the appropriate algorithm for LeetCode problem 1609. Even Odd Tree, let's use the Flowchart. Here's a detailed breakdown according to the flowchart's decision nodes and edges:
Is it a graph?
- Yes: Even though the problem describes a binary tree, it can be treated as a graph where nodes represent tree nodes and edges represent parent-child relationships.
Is it a tree?
- Yes: The problem explicitly states that it involves checking properties of a binary tree.
Is the problem related to directed acyclic graphs (DAGs)?
- No: While a binary tree is technically a DAG, the problem focuses on properties specific to binary trees and not on generalized DAG characteristics.
Is the problem related to shortest paths?
- No: The challenge involves verifying if tree levels meet certain parity (even/odd) conditions, not finding shortest paths.
Does the problem involve connectivity?
- No: Since the problem doesn’t require connecting or finding paths between disjoint parts of the tree, it doesn't concern connectivity.
Given the traversal through the flowchart, the decision arrives at using a DFS algorithm. However, in the context of this specific problem - checking properties level by level - a BFS approach is more suitable. This shows a limitation in the given decision flowchart, as it does not handle tree level-based operations explicitly, which is better managed with BFS. With BFS, we could verify the even/odd condition level-wise and ensure that nodes at each level of the tree satisfy the required criteria.
Conclusion: Even though the flowchart does not explicitly guide us to BFS for this tree level problem, BFS (Breadth-First Search) is apt for checking properties across tree levels, like in the Even Odd Tree problem. This suggests there could be a beneficial update to the flowchart for handling tree level-based tasks explicitly with BFS.
Intuition
To solve this problem, we use the Breadth-First Search (BFS) algorithm. BFS allows us to traverse the tree level by level. This fits our needs perfectly since the Even-Odd condition applies to individual levels of the tree.
Here's how we approach the solution:
- Initialize a queue and add the root node to it. The queue is used to keep track of nodes to visit in the current level.
- Traverse each level of the tree using a while loop that runs as long as there are nodes left in the queue:
- For each node, check if the value meets the required criteria based on whether the current level is even or odd.
- Maintain a
prev
value to compare with the current node's value ensuring the strictly increasing or decreasing order. - After processing all nodes in the current level, toggle the even/odd level flag using XOR with
1
.
- If at any point a node does not meet the requirements, return
false
. - If the loop completes without finding any violations, return
true
since the tree meets the Even-Odd condition.
By using BFS, we are able to check the values level by level, and by maintaining a variable to track the previous node's value, we can easily check the strictly increasing or decreasing order requirement.
Learn more about Tree, Breadth-First Search and Binary Tree patterns.
Solution Approach
The solution approach is based on a Breadth-First Search (BFS) pattern. Here's a walkthrough of the implementation details:
-
Initialize Variables: A flag variable
even
, which is initially set to1
, is used to represent the current parity of the level being traversed (odd or even). A queueq
is used to keep track of nodes in the current level.1even = 1 2q = deque([root])
-
BFS Loop: The solution iterates through the tree by using a
while
loop that continues as long as there are nodes in the queue.1while q:
-
Level Traversal: Within the loop, a
for
loop iterates over each node in the current level. The number of nodes is determined by the current size of the queue (len(q)
).1for _ in range(len(q)):
-
Initialization Per Level: At the beginning of each level, initialize
prev
to0
if the current level is supposed to contain even values, and toinf
for odd values.1prev = 0 if even else inf
-
Node Validation: For each node, the algorithm checks if the current node's value meets the appropriate conditions:
- For even levels, node values must be odd and increasing, checked by
root.val % 2 == 0 or prev >= root.val
. - For odd levels, node values must be even and decreasing, checked by
root.val % 2 == 1 or prev <= root.val
.
If a node does not meet its corresponding condition, the function returns
False
.1if even and (root.val % 2 == 0 or prev >= root.val): 2 return False 3if not even and (root.val % 2 == 1 or prev <= root.val): 4 return False
- For even levels, node values must be odd and increasing, checked by
-
Track Previous Value: The
prev
value is updated to the current node's value for the next iteration.1prev = root.val
-
Queue Update: The left and right children of the current node are added to the queue if they exist.
1if root.left: 2 q.append(root.left) 3if root.right: 4 q.append(root.right)
-
Toggle Even/Odd Level: After each level is processed, the
even
flag is toggled to1
if it was0
, or to0
if it was1
. The toggle is done by using the XOR operator (even ^= 1
).1even ^= 1
-
Completion: After the entire tree has been traversed without returning
False
, the function returnsTrue
, confirming that the tree satisfies the Even-Odd condition.
By using a queue to manage nodes, this approach maintains a clear delineation between levels and employs BFS efficiently to verify the tree against the provided conditions level by level.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take a small binary tree to illustrate the solution approach.
Suppose we have the following binary tree:
1 5 2 / \ 3 10 7 4 / / \ 5 6 12 2
Let's walk through the steps:
-
Initialize Variables: Set
even
to1
and put the root node with value 5 in the queue. -
BFS Loop: Start the while loop since the queue is not empty.
-
Level Traversal: Process nodes in the current level. We have one node, which is 5.
-
Initialization Per Level: At level 0 (even level), we initialize
prev
toinf
. -
Node Validation: We check the value of the root node:
- Since it's an even level, we expect an odd value and as it's the first value, it doesn't need to be increasing. The root's value is 5, which is odd, so it passes. The function continues.
-
Track Previous Value: The
prev
value becomes the current node's value, which is5
. -
Queue Update: Nodes
10
and7
are children of5
, so add them to the queue. -
Toggle Even/Odd Level: At the end of the level, toggle
even
to0
. -
BFS Loop: Now we have
10
and7
in the queue; the while loop continues. -
Level Traversal: There are two nodes in this level.
-
Initialization Per Level: Set
prev
to0
because we are at an odd level now. -
Node Validation: Evaluate the nodes in this odd level:
- We start with the node
10
. We expect an even value and decreasing order (however, as it's the first node of this level, we only check for an even value). Node10
has an even value, so it passes for now. - We move on to the next node in the same level, which is
7
. We expect an even value and a value less thanprev
(which is10
), but7
is odd, so it fails the condition.
- We start with the node
Since we detected a violation at node 7
, the function should return False
.
This small example contradicts the Even-Odd condition in the second level and illustrates the checking mechanism per level using BFS traversal.
Solution Implementation
1from collections import deque
2
3# Definition for a binary tree node.
4class TreeNode:
5 def __init__(self, val=0, left=None, right=None):
6 self.val = val
7 self.left = left
8 self.right = right
9
10class Solution:
11 def isEvenOddTree(self, root: TreeNode) -> bool:
12 # Initialize the level to 0 (0-indexed, so even)
13 level = 0
14
15 # Initialize the queue with the root node
16 queue = deque([root])
17
18 # Traverse the tree by levels
19 while queue:
20 # Depending on the current level, set the previous value accordingly
21 # For even levels, we start comparing from the smallest possible value (0)
22 # For odd levels, we start comparing from the largest possible value (infinity)
23 previous_value = 0 if level % 2 == 0 else float('inf')
24
25 # Process all nodes in the current level
26 for _ in range(len(queue)):
27 node = queue.popleft()
28
29 # Check the Even-Odd Tree condition for the current node
30 # At even levels, values must be odd and strictly increasing
31 if level % 2 == 0 and (node.val % 2 == 0 or previous_value >= node.val):
32 return False
33 # At odd levels, values must be even and strictly decreasing
34 if level % 2 == 1 and (node.val % 2 == 1 or previous_value <= node.val):
35 return False
36
37 # Update the previous value for the next comparison
38 previous_value = node.val
39
40 # Add child nodes to the queue
41 if node.left:
42 queue.append(node.left)
43 if node.right:
44 queue.append(node.right)
45
46 # Move to the next level
47 level += 1
48
49 # If all conditions are met, return True
50 return True
51
1// Definition of the binary tree node.
2class TreeNode {
3 int value;
4 TreeNode left;
5 TreeNode right;
6
7 TreeNode() {}
8
9 TreeNode(int value) {
10 this.value = value;
11 }
12
13 TreeNode(int value, TreeNode left, TreeNode right) {
14 this.value = value;
15 this.left = left;
16 this.right = right;
17 }
18}
19
20class Solution {
21 public boolean isEvenOddTree(TreeNode root) {
22 // Tracks whether the current level is even (starting with the root level as even).
23 boolean isLevelEven = true;
24
25 // Queue for performing level order traversal
26 Deque<TreeNode> queue = new ArrayDeque<>();
27 queue.offer(root);
28
29 // Loop while there are nodes in the queue
30 while (!queue.isEmpty()) {
31 // 'previousValue' will store the last value seen at the current level to check the strictly increasing or decreasing order.
32 int previousValue = isLevelEven ? 0 : 1000001;
33
34 // Number of nodes at the current level
35 for (int levelSize = queue.size(); levelSize > 0; --levelSize) {
36 root = queue.poll();
37
38 // For even levels, values must be odd and strictly increasing
39 if (isLevelEven && (root.value % 2 == 0 || previousValue >= root.value)) {
40 return false;
41 }
42
43 // For odd levels, values must be even and strictly decreasing
44 if (!isLevelEven && (root.value % 2 == 1 || previousValue <= root.value)) {
45 return false;
46 }
47
48 // Update the 'previousValue' with the current node's value
49 previousValue = root.value;
50
51 // Add the left and right children, if they exist, to the queue for the next level
52 if (root.left != null) {
53 queue.offer(root.left);
54 }
55 if (root.right != null) {
56 queue.offer(root.right);
57 }
58 }
59
60 // Toggle the level indication for the next level traversal
61 isLevelEven = !isLevelEven;
62 }
63
64 // If all levels meet the condition, return true
65 return true;
66 }
67}
68
1/**
2 * Definition for a binary tree node.
3 */
4struct TreeNode {
5 int val;
6 TreeNode *left;
7 TreeNode *right;
8 TreeNode() : val(0), left(nullptr), right(nullptr) {}
9 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10 TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11};
12
13class Solution {
14public:
15 /**
16 * Checks whether a binary tree is an even-odd tree.
17 * A binary tree is an even-odd tree if it meets the following conditions:
18 * - At even-indexed levels, all nodes' values are odd, and they are
19 * increasing from left to right.
20 * - At odd-indexed levels, all nodes' values are even, and they are
21 * decreasing from left to right.
22 *
23 * @param root The root of the binary tree.
24 * @return True if the binary tree is an even-odd tree, otherwise false.
25 */
26 bool isEvenOddTree(TreeNode* root) {
27 // 'isEvenLevel' indicates whether the current level is even or odd.
28 bool isEvenLevel = true;
29 // Queue for level order traversal.
30 queue<TreeNode*> nodeQueue{{root}};
31
32 while (!nodeQueue.empty()) {
33 // 'previousValue' holds the previously encountered value in the current level.
34 int previousValue = isEvenLevel ? 0 : INT_MAX; // Initialize based on the level.
35 // Process all nodes at the current level.
36 for (int i = nodeQueue.size(); i > 0; --i) {
37 root = nodeQueue.front();
38 nodeQueue.pop();
39 // Check whether the current node's value is appropriately odd or even.
40 if (isEvenLevel && (root->val % 2 == 0 || previousValue >= root->val)) return false;
41 if (!isEvenLevel && (root->val % 2 == 1 || previousValue <= root->val)) return false;
42
43 previousValue = root->val; // Update the 'previousValue'.
44 // Add child nodes to the queue for the next level.
45 if (root->left) nodeQueue.push(root->left);
46 if (root->right) nodeQueue.push(root->right);
47 }
48 // Toggle the level indicator after finishing each level.
49 isEvenLevel = !isEvenLevel;
50 }
51
52 return true; // The tree meets the even-odd tree conditions.
53 }
54};
55
1interface TreeNode {
2 val: number;
3 left: TreeNode | null;
4 right: TreeNode | null;
5}
6
7function isEvenOddTree(root: TreeNode | null): boolean {
8 // 'isEvenLevel' indicates whether the current level is even or odd.
9 let isEvenLevel = true;
10 // Queue for level order traversal.
11 let nodeQueue: (TreeNode | null)[] = [root];
12
13 while (nodeQueue.length > 0) {
14 // 'previousValue' holds the previously encountered value in the current level.
15 let previousValue: number = isEvenLevel ? 0 : Number.MAX_SAFE_INTEGER; // Initialize based on the level.
16 // Process all nodes at the current level.
17 let levelSize = nodeQueue.length;
18 for (let i = 0; i < levelSize; i++) {
19 let node = nodeQueue.shift()!; // '!' asserts that 'node' won't be null.
20 // Check whether the current node's value is appropriately odd or even.
21 if (isEvenLevel && (node.val % 2 === 0 || previousValue >= node.val)) return false;
22 if (!isEvenLevel && (node.val % 2 === 1 || previousValue <= node.val)) return false;
23
24 previousValue = node.val; // Update the 'previousValue'.
25 // Add child nodes to the queue for the next level.
26 if (node.left) nodeQueue.push(node.left);
27 if (node.right) nodeQueue.push(node.right);
28 }
29 // Toggle the level indicator after finishing each level.
30 isEvenLevel = !isEvenLevel;
31 }
32
33 return true; // The tree meets the even-odd tree conditions.
34}
35
Time and Space Complexity
// The time complexity of the provided code is O(n)
where n
is the number of nodes in the binary tree. This is because the code traverses each node exactly once. Each node is popped from the queue once, and its value is checked against the conditions for an even-odd tree, which takes constant time. The enqueue operations for the children of the nodes also happen once per node, maintaining the overall linear complexity with respect to the number of nodes.
// The space complexity of the code is O(m)
where m
is the maximum number of nodes at any level of the binary tree, or the maximum breadth of the tree. This is because the queue q
can at most contain all the nodes at the level with the maximum number of nodes at some point during execution, which determines the maximum amount of space needed at any time.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following is a min heap?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
Binary Tree Min Depth Prereq BFS on Tree problems bfs_intro Given a binary tree find the depth of the shallowest leaf node https algomonster s3 us east 2 amazonaws com binary_tree_min_depth png Explanation We can solve this problem with either DFS or BFS With DFS we traverse the whole tree looking for leaf nodes and record and update the minimum depth as we go With BFS though since we search level by level we are guaranteed to find the shallowest leaf node
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.