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

1. 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.
    
2. 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.
    
3. 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!