package Ġkat as . kotlin . leetcode . bst _ validation Ċ Ċ import Ġkat as . kotlin . leetcode . TreeNode Ċ import Ġdat sok . should Equal Ċ import Ġorg . junit . Test Ċ import Ġjava . util .* Ċ import Ġkotlin . Int . Companion . MAX _ VALUE Ċ import Ġkotlin . Int . Companion . MIN _ VALUE Ċ Ċ /** Ċ Ġ* Ġâľħ Ġhttps :// leetcode . com / problems / validate - binary - search - tree Ċ Ġ*/ Ċ class ĠValidate B ST Tests Ġ{ ĊĠĠĠ Ġprivate Ġfun ĠTreeNode . isValid () Ġ= ĠisValid _ 3 () ĊĊĠĠĠ Ġ@ Test Ġfun Ġ` sh allow Ġtrees `() Ġ{ ĊĠĠĠĠĠĠĠ ĠTreeNode ( 1 ). isValid () Ġshould Equal Ġtrue ĊĠĠĠĠĠĠĠ ĠTreeNode ( 1 , ĠTreeNode ( 0 )). isValid () Ġshould Equal Ġtrue ĊĠĠĠĠĠĠĠ ĠTreeNode ( 1 , Ġnull , ĠTreeNode ( 2 )). isValid () Ġshould Equal Ġtrue ĊĊĠĠĠĠĠĠĠ ĠTreeNode ( 1 , ĠTreeNode ( 2 )). isValid () Ġshould Equal Ġfalse ĊĠĠĠĠĠĠĠ ĠTreeNode ( 1 , Ġnull , ĠTreeNode ( 0 )). isValid () Ġshould Equal Ġfalse ĊĊĠĠĠĠĠĠĠ ĠTreeNode ( 1 , ĠTreeNode ( 1 )). isValid () Ġshould Equal Ġfalse ĊĠĠĠĠĠĠĠ ĠTreeNode ( 1 , Ġnull , ĠTreeNode ( 1 )). isValid () Ġshould Equal Ġfalse ĊĊĠĠĠĠĠĠĠ ĠTreeNode ( 0 , ĠTreeNode ( MIN _ VALUE ), ĠTreeNode ( MAX _ VALUE )). isValid () Ġshould Equal Ġtrue ĊĠĠĠĠĠĠĠ ĠTreeNode ( 0 , ĠTreeNode ( MAX _ VALUE ), ĠTreeNode ( MIN _ VALUE )). isValid () Ġshould Equal Ġfalse ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Test Ġfun Ġ` right Ġsubtree Ġhas Ġvalue Ġless Ġthan Ġor Ġequal Ġto Ġone Ġof Ġits Ġparents `() Ġ{ ĊĠĠĠĠĠĠĠ ĠTreeNode ( 4 , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġleft Ġ= ĠTreeNode ( 2 ), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġright Ġ= ĠTreeNode ( 6 , ĠTreeNode ( 5 ), ĠTreeNode ( 7 )) ĊĠĠĠĠĠĠĠ Ġ). isValid () Ġshould Equal Ġtrue ĊĠĠĠĠĠĠĠ ĠTreeNode ( 4 , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġleft Ġ= ĠTreeNode ( 2 ), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġright Ġ= ĠTreeNode ( 6 , ĠTreeNode ( 7 ), ĠTreeNode ( 5 )) ĊĠĠĠĠĠĠĠ Ġ). isValid () Ġshould Equal Ġfalse ĊĊĠĠĠĠĠĠĠ ĠTreeNode ( 4 , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġleft Ġ= ĠTreeNode ( 2 ), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġright Ġ= ĠTreeNode ( 6 , ĠTreeNode ( 1 ), ĠTreeNode ( 7 )) ĊĠĠĠĠĠĠĠ Ġ). isValid () Ġshould Equal Ġfalse ĊĊĠĠĠĠĠĠĠ ĠTreeNode ( 4 , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġleft Ġ= ĠTreeNode ( 2 ), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġright Ġ= ĠTreeNode ( 6 , ĠTreeNode ( 4 ), ĠTreeNode ( 7 )) ĊĠĠĠĠĠĠĠ Ġ). isValid () Ġshould Equal Ġfalse ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Test Ġfun Ġ` left Ġsubtree Ġhas Ġvalue Ġgreater Ġthan Ġone Ġof Ġits Ġparents `() Ġ{ ĊĠĠĠĠĠĠĠ ĠTreeNode ( 4 , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġleft Ġ= ĠTreeNode ( 2 , ĠTreeNode ( 1 ), ĠTreeNode ( 3 )), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġright Ġ= ĠTreeNode ( 6 ) ĊĠĠĠĠĠĠĠ Ġ). isValid () Ġshould Equal Ġtrue ĊĠĠĠĠĠĠĠ ĠTreeNode ( 4 , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġleft Ġ= ĠTreeNode ( 2 , ĠTreeNode ( 3 ), ĠTreeNode ( 1 )), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġright Ġ= ĠTreeNode ( 6 ) ĊĠĠĠĠĠĠĠ Ġ). isValid () Ġshould Equal Ġfalse ĊĊĠĠĠĠĠĠĠ ĠTreeNode ( 4 , ĊĠĠĠĠĠĠĠĠĠĠĠ Ġleft Ġ= ĠTreeNode ( 2 , ĠTreeNode ( 1 ), ĠTreeNode ( 5 )), ĊĠĠĠĠĠĠĠĠĠĠĠ Ġright Ġ= ĠTreeNode ( 6 ) ĊĠĠĠĠĠĠĠ Ġ). isValid () Ġshould Equal Ġfalse ĊĠĠĠ Ġ} Ċ } Ċ Ċ fun ĠisValid B ST ( root : ĠTreeNode ?): ĠBoolean Ġ{ ĊĠĠĠ Ġreturn Ġroot ?. isValid _ 1 () Ġ?: Ġtrue Ġ// Ġâľħ Ċ // ĠĠĠ Ġreturn Ġroot ?. isValid _ 2 () Ġ?: Ġtrue Ġ// Ġâľħ Ċ // ĠĠĠ Ġreturn Ġroot ?. isValid _ 3 () Ġ?: Ġtrue Ġ// Ġâľħ Ċ } Ċ Ċ private Ġfun ĠTreeNode . isValid _ 1 (): ĠBoolean Ġ{ ĊĠĠĠ Ġval Ġstack Ġ= ĠLinkedList < TreeNode >() ĊĠĠĠ Ġvar Ġnode : ĠTreeNode ? Ġ= Ġthis ĊĠĠĠ Ġvar Ġprev Node : ĠTreeNode ? Ġ= Ġnull ĊĊĠĠĠ Ġwhile Ġ( stack . isNotEmpty () Ġ|| Ġnode Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠ Ġwhile Ġ( node Ġ!= Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġstack . add Last ( node ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnode Ġ= Ġnode . left ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġnode Ġ= Ġstack . remove Last () ĊĠĠĠĠĠĠĠ Ġif Ġ( prev Node Ġ!= Ġnull Ġ&& Ġnode !!. value Ġ<= Ġprev Node . value ) Ġreturn Ġfalse ĊĠĠĠĠĠĠĠ Ġprev Node Ġ= Ġnode ĊĊĠĠĠĠĠĠĠ Ġnode Ġ= Ġnode . right ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġreturn Ġtrue Ċ } Ċ Ċ private Ġclass ĠRef < T >( var Ġvalue : ĠT ? Ġ= Ġnull ) Ċ Ċ private Ġfun ĠTreeNode . isValid _ 2 ( last : ĠRef < TreeNode > Ġ= ĠRef ()): ĠBoolean Ġ{ ĊĠĠĠ Ġif Ġ( left Ġ!= Ġnull Ġ&& Ġ! left !!. isValid _ 2 ( last )) Ġreturn Ġfalse ĊĊĠĠĠ Ġif Ġ( last . value Ġ!= Ġnull Ġ&& Ġlast . value !!. value Ġ>= Ġvalue ) Ġreturn Ġfalse ĊĠĠĠ Ġlast . value Ġ= Ġthis ĊĊĠĠĠ Ġif Ġ( right Ġ!= Ġnull Ġ&& Ġ! right !!. isValid _ 2 ( last )) Ġreturn Ġfalse ĊĊĠĠĠ Ġreturn Ġtrue Ċ } Ċ Ċ private Ġfun ĠTreeNode . isValid _ 3 ( min : ĠInt ? Ġ= Ġnull , Ġmax : ĠInt ? Ġ= Ġnull ): ĠBoolean Ġ{ ĊĠĠĠ Ġif Ġ( min Ġ!= Ġnull Ġ&& Ġvalue Ġ<= Ġmin ) Ġreturn Ġfalse ĊĠĠĠ Ġif Ġ( max Ġ!= Ġnull Ġ&& Ġvalue Ġ> Ġmax ) Ġreturn Ġfalse ĊĊĠĠĠ Ġif Ġ( left Ġ!= Ġnull Ġ&& Ġleft !!. value Ġ>= Ġvalue ) Ġreturn Ġfalse ĊĠĠĠ Ġif Ġ( right Ġ!= Ġnull Ġ&& Ġright !!. value Ġ<= Ġvalue ) Ġreturn Ġfalse ĊĊĠĠĠ Ġreturn Ġleft ?. isValid _ 3 ( min Ġ= Ġmin , Ġmax Ġ= Ġvalue ) Ġ?: Ġtrue Ġ&& ĊĠĠĠĠĠĠĠĠĠĠ Ġright ?. isValid _ 3 ( min Ġ= Ġvalue , Ġmax Ġ= Ġmax ) Ġ?: Ġtrue Ċ } Ċ