CODE:

//C++ program to check if a tree is sorted level-wise or not
/*                  1
                  /   
                 2     3
               /     / 
              4    5 6   7
*/

#include<iostream>
#include <bits/stdc++.h>  
#include<queue>
using namespace std; 

/*When the data is other than string then this template will be used*/
template <typename T>	
struct Value
{
   T data;
   Value()
   {
      data = 0;
   }
};

template <>		//When the data is string then this template will be used
struct Value <string>
{
   string data;
   Value()
   {
      data.assign("");
   }
};

template <typename T>		//creating a new node
struct Node
{
   Value<T> data;
   Node<T>* left=nullptr;
   Node<T>* right=nullptr;
};

template <typename T>		//function template to create binary tree
Node<T>* createTree()
{
   //creating all nodes needed in the binary tree
   Node<T>* node1 = new Node<T>; 
   node1->data.data = 1;
   Node<T>* node2 = new Node<T>; 
   node2->data.data = 2;
   Node<T>* node3 = new Node<T>; 
   node3->data.data = 3;
   Node<T>* node4 = new Node<T>;
   node4->data.data = 4;
   Node<T>* node5 = new Node<T>; 
   node5->data.data = 5;
   Node<T>* node6 = new Node<T>; 
   node6->data.data = 6;
   Node<T>* node7 = new Node<T>; 
   node7->data.data = 7;
   
   //connecting nodes to create a binary tree
   node1->left = node2;
   node1->right = node3;
   node2->left = node4;
   node2->right = node5;
   node3->left = node6;
   node3->right = node7;
   

   return node1;	//returning the root node as it is connected to every node
}

template <typename T>
int isSorted(Node<T>* root)
{  
	int prevMax = INT_MIN,minval,maxval,levelSize;  
	 
	queue<Node<T> *> q;	//using queue to perform level order traversal 
	q.push(root); 

	while (!q.empty())
        {  
	levelSize = q.size(); //finding no. of nodes in current level
		
	/*Storing minimum and maximum value of the level*/
	minval = INT_MAX; 
	maxval = INT_MIN; 

	while (levelSize > 0)	//traversing the level for finding the min and max value 
	{ 
		root = q.front(); 
		q.pop(); 
		levelSize--; 
			
		/*using the min and max function to determine the value*/
		minval = min(minval, root->data.data); 
		maxval = max(maxval, root->data.data); 

		if (root->left) 
            		q.push(root->left); 

		if (root->right) 
	         	q.push(root->right); 
		} 

                /*if minimum value of current level is not greater than the max value
                 of previous level then the tree is not sorted*/
		if (minval <= prevMax) 
			return 0;                  //this means not sorted
                /*maximum value of this level will become the previous maximum value
                for next level*/
		prevMax = maxval; 
	} 

	return 1;  //if sorted 
} 

int main() 
{ 
	Node<int>* root = createTree<int>();  //creating tree
	if (isSorted(root)) 
		cout << "Sorted"<<endl; 
	else
		cout << "Not sorted"<<endl; 
	return 0; 
}