# Check if a binary tree contains node values are in strictly increasing and decreasing order at even and odd levels

## Introduction

A Binary Tree is a __Data Structure__ having a root node and at most two children nodes. Each of these children forms the left subtree and the right subtree. The end nodes or the leaf nodes have no children and are pointed by a __NULL__ pointer.

## Problem Statement

Given a binary tree, check if it consists of node values in strictly increasing order at even levels and strictly decreasing at odd levels.

**Note: **Assume that root is at level 0(even).

## Solution Approach

Since we are concerned with the even and odd levels, we need to approach this problem through level order traversal. We will traverse the whole tree level-wise starting from level 0. Every time we’re on an odd level, check if the numbers on this level are in decreasing order. Every time we’re on an even level, check if the numbers on this level are in increasing order. If not, return false immediately. If yes, move forward and keep checking for the next levels.

**Checking for ascending and descending order:**

Store the numbers of a level in a vector. For checking if the numbers are in increasing order, we use the function is_sorted(). For checking if the numbers are in decreasing order, reverse the vector and use the function is_sorted().

**Note**: is_sorted() is a function that checks if the vector is sorted in ascending order or not. It returns true if the vector is sorted, otherwise false.

Steps are:

- Construct a binary tree.

- Call the odd_even_level() function with the root of the tree as the parameter.

- Push the root node into the queue.

- While the queue is not empty,
- Keep popping the nodes of the current level, insert these nodes in a vector and insert the children of the node in the queue.

- Once all the elements of a current level are inserted into the vector, check if it’s in the increasing order if the level number is even and in decreasing order if the level number is odd using the is_sorted() function.

- If, on any level, the order is not followed, return false. Otherwise, move to the next level.

- Return true at the end of the whole tree is traversed.

- Keep popping the nodes of the current level, insert these nodes in a vector and insert the children of the node in the queue.
- Print “Yes” if the value returned by the function is true. Otherwise, print “No.”

### C++ implementation

Below is the C++ implementation of the above-discussed approach:

```
#include<bits/stdc++.h>
using namespace std;
template <typename T>
class BinaryTreeNode{ // Class for BinaryTreeNode
public:
T data; // Data of the node
BinaryTreeNode* left; // Left of the node
BinaryTreeNode* right; // Right of the node
BinaryTreeNode(T data){ // Constructor for assigning the data to the current node
this->data=data;
left=NULL;
right=NULL;
}
};
bool checkEvenOddLevel(BinaryTreeNode<int> *root)
{
if (root == NULL) // If the root itself is NULL, return true
return true;
// Queue for storing nodes of each level
queue<BinaryTreeNode<int>*> q;
q.push(root); // Push the root in the queue
int level = 0; // Stores the current level number we are at
// Until the q is empty
while (q.empty())
{
vector<int> v; // Vector for storing the nodes of the current level
int size = q.size();
for(int i = 0; i < size; i++) // Traverse each node of the current node
{
BinaryTreeNode<int> *node = q.front();
v.push_back(node->data); // Push the current node into the vector
// Insert left and right child of node into the queue
if (node->left != NULL)
q.push(node->left);
if (node->right != NULL)
q.push(node->right);
}
// If the level is even
if (level % 2 == 0){
// Using the is_sorted inbuilt function for finding if the vector is sorted
if(!is_sorted(v.begin(),v.end())){
return false;
}
}
// If the level is odd
else if (level % 2 == 1){
//Since the vector in this case should be in decreasing order,
//we first reverse the vector and then check if it is in increasing order
reverse(v.begin(),v.end());
if(!is_sorted(v.begin(),v.end())){
return false;
}
}
// Increment the level count
level++;
}
return true;
}
// Driver Code
int main()
{
// Construct a Binary Tree
BinaryTreeNode<int> *root = NULL;
root = new BinaryTreeNode<int>(2);
root->left = new BinaryTreeNode<int>(6);
root->right = new BinaryTreeNode<int>(3);
root->left->left = new BinaryTreeNode<int>(4);
root->left->right = new BinaryTreeNode<int>(7);
root->right->right = new BinaryTreeNode<int>(11);
root->left->left->left = new BinaryTreeNode<int>(10);
root->left->left->right = new BinaryTreeNode<int>(5);
root->left->right->right = new BinaryTreeNode<int>(1);
// Function Call
if (checkEvenOddLevel(root))
cout << "YES"<<endl;
else
cout << "NO"<<endl;
}
```

#### Output

`YES`

### Complexities

#### Time complexity

O(n), where n is the number of nodes in the tree.

**Reason**: We have to traverse the whole tree once level by level. Therefore, the time complexity is O(n).

#### Space complexity

O(n), where n is the number of nodes in the tree.

**Reason**: We store each node of each level once in the vector. Therefore, the space complexity is O(n).

## Frequently asked questions

**What is a binary tree?**

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

**What is a binary tree used for?**

In computing, binary trees are mainly used for**searching and sorting**as they provide a means to store data hierarchically.

**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.

## Key Takeaways

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.**

You can look for more problems based on the binary tree. Some of these are the __largest number in a binary tree__, __triplets in a binary tree__, __maximum depth of a binary tree__, __LCA of a binary tree__, __minimum depth in a binary tree__, and __height of the binary tree__. These questions are asked during various __coding contests__ as well as __placements tests.__

To practice more such problems, __Codestudio__ is a one-stop destination. This platform will help you acquire effective coding techniques and give you an overview of student interview experience in various product-based companies.

Happy Coding!

Comments

## No comments yet

## Be the first to share what you think