C++ program to check if a tree is sorted level-wise or not

C++ program to check if a tree is sorted level-wise or not

In this program we are checking if the tree is sorted level-wise or not.We will do level order traversal and then keep the track of maximum andminimum element of the (i)th level then we will compare the maximum element of ith level with minimum element of (i+1)th level Like this we will find if the tree is sorted or not .Here in this program we are using Template for a genral tree and queue to check for level wise.I have hardcoded the binary tree because if we take it from user then we need ask for two traversal methods and many more thing .So here i have hardcoded the binary tree so to explain the function how to check binary tree if sorted or not.

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

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

/*When the data is other than string then this template will be used*/
template <typename T>
T data;
data = 0;

template <> //When the data is string then this template will be used
struct Value <string>
string data;

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

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();

/*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)

if (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;
cout << "Not sorted"<<endl;
return 0;