Check if a binary tree is sorted level | Java 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
import java . util . * ; class GfG { static class Node { int key ; Node left , right ; } static Node newNode ( int key ) { Node temp = new Node ( ) ; temp . key = key ; temp . left = null ; temp . right = null ; return temp ; } static int isSorted ( Node root ) { int prevMax = Integer . MIN_VALUE ; int minval ; int maxval ; int levelSize ; Queue < Node > q = new LinkedList < Node > ( ) ; q . add ( root ) ; while ( ! q . isEmpty ( ) ) { levelSize = q . size ( ) ; minval = Integer . MAX_VALUE ; maxval = Integer . MIN_VALUE ; while ( levelSize > 0 ) { root = q . peek ( ) ; q . remove ( ) ; levelSize -- ; minval = Math . min ( minval , root . key ) ; maxval = Math . max ( maxval , root . key ) ; if ( root . left != null ) q . add ( root . left ) ; if ( root . right != null ) q . add ( root . right ) ; } if ( minval <= prevMax ) return 0 ; prevMax = maxval ; } return 1 ; } public static void main ( String [ ] args ) { 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 ) == 1 ) System . out . println ( " Sorted " ) ; else System . out . println ( " Not ▁ sorted " ) ; } }