Find if given vertical level of binary tree is sorted or not | CPP program to determine whether vertical level l of binary tree is sorted or not . ; Structure of a tree node . ; Function to create new tree node . ; Helper function to determine if vertical level l of given binary tree is sorted or not . ; If root is null , then the answer is an empty subset and an empty subset is always considered to be sorted . ; Variable to store previous value in vertical level l . ; Variable to store current level while traversing tree vertically . ; Variable to store current node while traversing tree vertically . ; Declare queue to do vertical order traversal . A pair is used as element of queue . The first element in pair represents the node and the second element represents vertical level of that node . ; Insert root in queue . Vertical level of root is 0. ; Do vertical order traversal until all the nodes are not visited . ; Check if level of node extracted from queue is required level or not . If it is the required level then check if previous value in that level is less than or equal to value of node . ; If left child is not NULL then push it in queue with level reduced by 1. ; If right child is not NULL then push it in queue with level increased by 1. ; If the level asked is not present in the given binary tree , that means that level will contain an empty subset . Therefore answer will be true . ; Driver program ; 1 / \ 2 5 / \ 7 4 / 6
#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 ; } bool isSorted ( Node * root , int level ) { if ( root == NULL ) return true ; int prevVal = INT_MIN ; int currLevel ; Node * currNode ; queue < pair < Node * , int > > q ; q . push ( make_pair ( root , 0 ) ) ; while ( ! q . empty ( ) ) { currNode = q . front ( ) . first ; currLevel = q . front ( ) . second ; q . pop ( ) ; if ( currLevel == level ) { if ( prevVal <= currNode -> key ) prevVal = currNode -> key ; else return false ; } if ( currNode -> left ) q . push ( make_pair ( currNode -> left , currLevel - 1 ) ) ; if ( currNode -> right ) q . push ( make_pair ( currNode -> right , currLevel + 1 ) ) ; } return true ; } int main ( ) { Node * root = newNode ( 1 ) ; root -> left = newNode ( 2 ) ; root -> right = newNode ( 5 ) ; root -> left -> left = newNode ( 7 ) ; root -> left -> right = newNode ( 4 ) ; root -> left -> right -> left = newNode ( 6 ) ; int level = -1 ; if ( isSorted ( root , level ) == true ) cout << " Yes " ; else cout << " No " ; return 0 ; }