Check if a binary tree is sorted level | CPP program to determine whether binary tree is level sorted or not . ; Structure of a tree node . ; Function to create new tree node . ; Function to determine if given binary tree is level sorted or not . ; to store maximum value of previous level . ; to store minimum value of current level . ; to store maximum value of current level . ; to store number of nodes in current level . ; queue to perform level order traversal . ; find number of nodes in current level . ; traverse current level and find minimum and maximum value of this level . ; if minimum value of this level is not greater than maximum value of previous level then given tree is not level sorted . ; maximum value of this level is previous maximum value for next level . ; Driver program ; 1 / 4 \ 6 / \ 8 9 / \ 12 10
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int key ; Node * left , * right ; } ; Node * newNode ( int key ) { Node * temp = new Node ; temp -> key = key ; temp -> left = temp -> right = NULL ; return temp ; } int isSorted ( Node * root ) { int prevMax = INT_MIN ; int minval ; int maxval ; int levelSize ; queue < Node * > q ; q . push ( root ) ; while ( ! q . empty ( ) ) { levelSize = q . size ( ) ; minval = INT_MAX ; maxval = INT_MIN ; while ( levelSize > 0 ) { root = q . front ( ) ; q . pop ( ) ; levelSize -- ; minval = min ( minval , root -> key ) ; maxval = max ( maxval , root -> key ) ; if ( root -> left ) q . push ( root -> left ) ; if ( root -> right ) q . push ( root -> right ) ; } if ( minval <= prevMax ) return 0 ; prevMax = maxval ; } return 1 ; } int main ( ) { Node * root = newNode ( 1 ) ; root -> left = newNode ( 4 ) ; root -> left -> right = newNode ( 6 ) ; root -> left -> right -> left = newNode ( 8 ) ; root -> left -> right -> right = newNode ( 9 ) ; root -> left -> right -> left -> left = newNode ( 12 ) ; root -> left -> right -> right -> right = newNode ( 10 ) ; if ( isSorted ( root ) ) cout << " Sorted " ; else cout << " Not ▁ sorted " ; return 0 ; }