Do you think IIT Guwahati certified course can help you in your career?
Introduction
A Binary Tree is a Data Structure having a root node and, at most, two children nodes. Here in this article, we will be going to understand a very famous problem. This problem is related to the binary trees, which is already asked in many top companies like Facebook, Google and Microsoft.
Problem Statement
Given a binary tree, write a function to determine if the node values are in a strictly increasing order for nodes at even levels and a strictly decreasing order for nodes at odd levels. Where we assume the root node is at 0 level.
Example
Input
Output
True
Explanation
In the above example, level 0 is 2, and the number contained in odd level 1 is 8 and 3, which is strictly decreasing. As it satisfies the condition.
Similarly, In even level 2, numbers are 5,7,9 and 10, which are in increasing order. It also satisfies the condition.
The last odd level 3 numbers are 9,3, and 1, which are in decreasing order. It also satisfies the condition. So the overall result is true.
Approach
The approach to check if a binary tree contains node values in strictly increasing and decreasing order at even and odd levels:
Perform a level-order traversal of the binary tree, keeping track of the level of each node.
For each level, check if the node values are in strictly increasing order for even levels and strictly decreasing order for odd levels.
If all levels satisfy the condition, return true. Otherwise, return false.
To implement this approach, we can use a queue data structure to perform the level-order traversal of the binary tree. We can keep track of the level of each node by adding an additional value to the tuple representing each node in the queue.
During the level-order traversal, we can keep track of the current level and the previous node value. For each level, we check if the node values are in strictly increasing order for even levels and strictly decreasing order for odd levels. If any level does not satisfy the condition, we can immediately return false.
Algorithm
Below is the algorithm:
Check if the root of the binary tree is null, and return true if so.
Initialise a queue with the root of the binary tree and variables to track the current level and the last value processed.
While the queue is not empty, dequeue the next node and add its value to a list of values for the current level.
Check if the value of the node is greater or smaller than the last value processed, depending on the level of the node. If the condition is violated, set the flag to false.
Enqueue the left and right child nodes of the current node if they exist.
Increment the level counter, and repeat the above steps for the next level.
Return the flag, which indicates if the binary tree satisfies the required conditions.
Dry Run
Consider the following binary tree:
Starting at the root node with value 2, we perform a level-order traversal using a queue. We keep track of the current level of the tree and a flag indicating if the nodes in that level have values that satisfy the required conditions.
First, we add the root node to the queue and set the level to 0.
While the queue is not empty, we process each node in the queue for the current level.
We check if the value of the node is even or odd depending on the level, and if it does not satisfy the condition, we set the flag to false.
We also check if the value of the node is greater than the value of the previous node in the current level in case of even level( To satisfy increasing order). If it is not, we set the flag to false.
Similarly, we will also check if the value of the node is smaller than the value of the previous node in the current level in case of odd level( To satisfy decreasing order). If it is not, we set the flag to false.
If all nodes in the current level satisfy the conditions, we continue with the next level.
We repeat the above steps until we have processed all nodes in the tree.
If the flag is still true after processing all nodes, we return true to indicate that the binary tree satisfies the required conditions. Otherwise, we return false.
In this example, the binary tree satisfies the required conditions since all nodes in even levels are increasing and in odd levels are decreasing. Therefore, the function would return true.
C++ implementation
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class CNode {
public:
int val;
CNode* left;
CNode* right;
CNode(int v) {
val = v;
left = nullptr;
right = nullptr;
}
};
bool checkEvenOddLevels(CNode* root) {
// Return true if the root node is null
if (root == nullptr) {
return true;
}
// Create a queue to store the nodes of the tree in level order
queue<CNode*> q;
q.push(root);
// Initialize the level to 0, the last value seen to 0, and the flag to true
int level = 0;
int last = 0;
bool flag = true;
// While the queue is not empty, process the nodes in each level
while (!q.empty()) {
// Get the number of nodes in the current level
int size = q.size();
// Process the nodes in the current level
for (int i = 0; i < size; i++) {
// Get the first node in the queue
CNode* temp = q.front();
q.pop();
// Add the left and right child nodes to the queue if they exist
if (temp->left != nullptr) {
q.push(temp->left);
}
if (temp->right != nullptr) {
q.push(temp->right);
}
// Check if the level is even
if (level % 2 == 0) {
// Check if the value of the current node is greater than the last value seen
if (i != 0 && temp->val <= last) {
flag = false;
}
}
else {
// For Odd levels
// Check if the value of the current node is less than the last value seen
if (i != 0 && temp->val >= last) {
flag = false;
}
}
// Update the last value seen to the value of the current node
last = temp->val;
}
// Increment the level counter
level++;
}
// Return the flag indicating if the binary tree satisfies the conditions
return flag;
}
int main() {
CNode* root = new CNode(2);
root->left = new CNode(8);
root->right = new CNode(3);
root->left->left = new CNode(5);
root->left->right = new CNode(7);
root->right->left = new CNode(9);
root->right->right = new CNode(10);
if (checkEvenOddLevels(root)) {
cout << "The binary tree satisfies the conditions." << endl;
}
else {
cout << "The binary tree does not satisfy the conditions." << endl;
}
return 0;
}
Main Function Parameter
2
/ \
8 3
/ \ / \
5 7 9 10
Output
Java Implementation
import java.util.*;
// Define the CNode class with integer value, left child, and right child
class CNode {
int val;
CNode left;
CNode right;
public CNode(int val) {
this.val = val;
left = null;
right = null;
}
}
class Solution {
// Define the checkEvenOddLevels function that takes a root node and returns a boolean value
public static boolean checkEvenOddLevels(CNode root) {
// Return true if the root node is null
if (root == null) {
return true;
}
// Create a queue to store the nodes of the tree in level order
Queue<CNode> queue = new LinkedList<>();
queue.add(root);
// Initialize the level to 0, the last value seen to 0, and the flag to true
int level = 0;
int last = 0;
boolean flag = true;
// While the queue is not empty, process the nodes in each level
while (!queue.isEmpty()) {
// Get the number of nodes in the current level
int size = queue.size();
// Process the nodes in the current level
for (int i = 0; i < size; i++) {
// Get the first node in the queue
CNode temp = queue.poll();
// Add the left and right child nodes to the queue if they exist
if (temp.left != null) {
queue.add(temp.left);
}
if (temp.right != null) {
queue.add(temp.right);
}
// Check if the level is even
if (level % 2 == 0) {
// Check if the value of the current node is greater than the last value seen
if (i != 0 && temp.val <= last) {
flag = false;
}
}
else {
// Check of odd levels
// Check if the value of the current node is less than the last value seen
if (i != 0 && temp.val >= last) {
flag = false;
}
}
// Update the last value seen to the value of the current node
last = temp.val;
}
// Increment the level counter
level++;
}
// Return the flag indicating if the binary tree satisfies the conditions
return flag;
}
public static void main(String[] args) {
// Create a binary tree with the root node having value 1, two children with values 3 and 5, and so on
CNode root = new CNode(2);
root.left = new CNode(8);
root.right = new CNode(3);
root.left.left = new CNode(5);
root.left.right = new CNode(7);
root.right.left = new CNode(9);
root.right.right = new CNode(10);
// Call the checkEvenOddLevels function on the binary tree
boolean result = checkEvenOddLevels(root);
// Print the result
if (result) {
System.out.println("The binary tree satisfies the conditions.");
} else {
System.out.println("The binary tree does not satisfy the conditions.");
}
}
}
Main Function Parameter
2
/ \
8 3
/ \ / \
5 7 9 10
Output
Complexities
Time complexity
O(N), where n is the number of nodes in the tree.
Reason: This is because we are visiting each node once and processing its value and children.
Space Complexity
O(W), where W is the width of the binary tree.
Reason: This is because we are using a queue to store the nodes to be processed, and at most, we will have all the nodes of a level in the queue. In the worst-case scenario, the binary tree is a complete binary tree, so the width is O(n). In this case, the space complexity is O(n).
Frequently asked questions
What is the purpose of the algorithm?
The purpose of the algorithm is to determine if a given binary tree is an Even-Odd Tree. The algorithm checks if the values of the nodes in the tree follow the strict order pattern defined for Even-Odd Trees.
What is an Even-Odd Tree?
An Even-Odd Tree is a binary tree where all the values in the nodes of even levels (the root is considered level 0) are in strictly increasing order, and all the values in the nodes of odd levels are in strictly decreasing order.
How to find out if an array/vector is sorted in increasing?
One way to check is to traverse the whole array/vector and see if each current element is greater than its previous element.
Another way is to use the in-built is_sorted() function. It returns true if the array/vector is sorted in ascending order. Otherwise false.
What is the difference between a binary tree and a binary search tree?
A binary tree is a general data structure, while a binary search tree is a special type of binary tree that satisfies a specific ordering property: for any given node, all nodes in its left subtree must have values less than the node's value, and all nodes in its right subtree must have values greater than the node's value.
What is the height of a binary tree?
The height of a binary tree is the number of edges on the longest path from the root to a leaf node.
Conclusion
In this article, we’ve discussed a problem related to the binary tree. To solve it, we traversed the whole tree level by level. This kind of traversal is called Breadth-first traversal.
240+ registered 
