1609. Even Odd Tree

MediumTreeBreadth-First SearchBinary 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 to 1, is used to represent the current parity of the level being traversed (odd or even). A queue q is used to keep track of nodes in the current level.
```
even = 1
q = 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.
```
while 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)).
```
for _ in range(len(q)):
```
Initialization Per Level: At the beginning of each level, initialize prev to 0 if the current level is supposed to contain even values, and to inf for odd values.
```
prev = 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.

if even and (root.val % 2 == 0 or prev >= root.val):
    return False
if not even and (root.val % 2 == 1 or prev <= root.val):
    return False

Track Previous Value: The prev value is updated to the current node's value for the next iteration.
```
prev = root.val
```

Queue Update: The left and right children of the current node are added to the queue if they exist.

if root.left:
    q.append(root.left)
if root.right:
    q.append(root.right)

Toggle Even/Odd Level: After each level is processed, the even flag is toggled to 1 if it was 0, or to 0 if it was 1. The toggle is done by using the XOR operator (even ^= 1).
```
even ^= 1
```
Completion: After the entire tree has been traversed without returning False, the function returns True, 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 Evaluator

Example Walkthrough

Let's take a small binary tree to illustrate the solution approach.

Suppose we have the following binary tree:

Let's walk through the steps:

Initialize Variables: Set even to 1 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 to inf.
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 is 5.
Queue Update: Nodes 10 and 7 are children of 5, so add them to the queue.
Toggle Even/Odd Level: At the end of the level, toggle even to 0.
BFS Loop: Now we have 10 and 7 in the queue; the while loop continues.
Level Traversal: There are two nodes in this level.
Initialization Per Level: Set prev to 0 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). Node 10 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 than prev (which is 10), but 7 is odd, so it fails the condition.

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which algorithm should you use to find a node that is close to the root of the tree?

DFS

BFS

Binary search

Backtracking

I don’t know