package Ġdata _ structures . tree Ċ Ċ import Ġcom . google . common . truth . Truth . assertThat Ċ import Ġorg . junit . jupiter . api . BeforeEach Ċ import Ġorg . junit . jupiter . api . Test Ċ Ċ internal Ġclass ĠBinary Search Tree Test Ġ{ ĊĊĠĠĠ Ġprivate Ġlateinit Ġvar Ġtree : ĠBinary Search Tree < Int > ĊĊĠĠĠ Ġ@ BeforeEach ĊĠĠĠ Ġfun Ġsetup () Ġ{ ĊĠĠĠĠĠĠĠ Ġtree Ġ= ĠBinary Search Tree () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Test ĊĠĠĠ Ġfun Ġtest IsEmpty () Ġ{ ĊĠĠĠĠĠĠĠ ĠassertThat ( tree . isEmpty ()). isTrue () ĊĠĠĠĠĠĠĠ Ġtree . add ( 1 ) ĊĠĠĠĠĠĠĠ ĠassertThat ( tree . isEmpty ()). isFalse () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Test ĊĠĠĠ Ġfun Ġtest Size () Ġ{ ĊĠĠĠĠĠĠĠ ĠassertThat ( tree . size ()). isEqualTo ( 0 ) ĊĠĠĠĠĠĠĠ Ġtree . add ( 1 ) ĊĠĠĠĠĠĠĠ Ġtree . add ( 2 ) ĊĠĠĠĠĠĠĠ Ġtree . add ( 3 ) ĊĠĠĠĠĠĠĠ ĠassertThat ( tree . size ()). isEqualTo ( 3 ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Test ĊĠĠĠ Ġfun Ġtest Height () Ġ{ ĊĠĠĠĠĠĠĠ ĠassertThat ( tree . height ()). isEqualTo ( 0 ) ĊĠĠĠĠĠĠĠ Ġtree . add ( 1 2 ) ĊĠĠĠĠĠĠĠ ĠassertThat ( tree . height ()). isEqualTo ( 1 ) ĊĠĠĠĠĠĠĠ Ġtree . add ( 5 ) ĊĠĠĠĠĠĠĠ Ġtree . add ( 1 6 ) ĊĠĠĠĠĠĠĠ ĠassertThat ( tree . height ()). isEqualTo ( 2 ) ĊĠĠĠĠĠĠĠ Ġtree . add ( 3 ) ĊĠĠĠĠĠĠĠ Ġtree . add ( 1 4 ) ĊĠĠĠĠĠĠĠ Ġtree . add ( 2 0 ) ĊĠĠĠĠĠĠĠ ĠassertThat ( tree . height ()). isEqualTo ( 3 ) ĊĠĠĠĠĠĠĠ Ġtree . add ( 1 ) ĊĠĠĠĠĠĠĠ ĠassertThat ( tree . height ()). isEqualTo ( 4 ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Test ĊĠĠĠ Ġfun Ġtest Add () Ġ{ ĊĠĠĠĠĠĠĠ ĠassertThat ( tree . add ( 1 )). isTrue () ĊĠĠĠĠĠĠĠ ĠassertThat ( tree . add ( 2 )). isTrue () ĊĠĠĠĠĠĠĠ ĠassertThat ( tree . add ( 1 )). isFalse () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Test ĊĠĠĠ Ġfun Ġtest Remove () Ġ{ ĊĠĠĠĠĠĠĠ Ġtree . add ( 1 ) ĊĠĠĠĠĠĠĠ ĠassertThat ( tree . size ()). isEqualTo ( 1 ) ĊĠĠĠĠĠĠĠ ĠassertThat ( tree . remove ( 2 )). isFalse () ĊĠĠĠĠĠĠĠ ĠassertThat ( tree . size ()). isEqualTo ( 1 ) ĊĠĠĠĠĠĠĠ ĠassertThat ( tree . remove ( 1 )). isTrue () ĊĠĠĠĠĠĠĠ ĠassertThat ( tree . isEmpty ()). isTrue () ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Test ĊĠĠĠ Ġfun Ġtest Build Bal anced Tree () Ġ{ ĊĠĠĠĠĠĠĠ Ġtree . add ( 5 ) ĊĠĠĠĠĠĠĠ Ġtree . add ( 4 ) ĊĠĠĠĠĠĠĠ Ġtree . add ( 3 ) ĊĠĠĠĠĠĠĠ Ġtree . add ( 2 ) ĊĠĠĠĠĠĠĠ Ġtree . add ( 1 ) ĊĠĠĠĠĠĠĠ ĠassertThat ( tree . height ()). isEqualTo ( 5 ) ĊĠĠĠĠĠĠĠ Ġtree . build Bal anced Tree () ĊĠĠĠĠĠĠĠ ĠassertThat ( tree . height ()). isEqualTo ( 3 ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Test ĊĠĠĠ Ġfun Ġtest In order () Ġ{ ĊĠĠĠĠĠĠĠ Ġtree . add ( 1 ) ĊĠĠĠĠĠĠĠ Ġtree . add ( 3 ) ĊĠĠĠĠĠĠĠ Ġtree . add ( 5 ) ĊĠĠĠĠĠĠĠ Ġtree . add ( 7 ) ĊĠĠĠĠĠĠĠ Ġtree . add ( 1 0 ) ĊĠĠĠĠĠĠĠ Ġtree . add ( 2 ) ĊĠĠĠĠĠĠĠ Ġtree . build Bal anced Tree () ĊĠĠĠĠĠĠĠ Ġval Ġexpected Ġ= ĠlistOf ( 1 , Ġ 2 , Ġ 3 , Ġ 5 , Ġ 7 , Ġ 1 0 ) ĊĠĠĠĠĠĠĠ ĠassertThat ( tree . in order ()). isEqualTo ( expected ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Test ĊĠĠĠ Ġfun Ġtest Pre order () Ġ{ ĊĠĠĠĠĠĠĠ Ġtree . add ( 1 ) ĊĠĠĠĠĠĠĠ Ġtree . add ( 3 ) ĊĠĠĠĠĠĠĠ Ġtree . add ( 5 ) ĊĠĠĠĠĠĠĠ Ġtree . add ( 7 ) ĊĠĠĠĠĠĠĠ Ġtree . add ( 1 0 ) ĊĠĠĠĠĠĠĠ Ġtree . add ( 2 ) ĊĠĠĠĠĠĠĠ Ġtree . build Bal anced Tree () ĊĠĠĠĠĠĠĠ Ġval Ġexpected Ġ= ĠlistOf ( 3 , Ġ 1 , Ġ 2 , Ġ 7 , Ġ 5 , Ġ 1 0 ) ĊĠĠĠĠĠĠĠ ĠassertThat ( tree . pre order ()). isEqualTo ( expected ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Test ĊĠĠĠ Ġfun Ġtest Post order () Ġ{ ĊĠĠĠĠĠĠĠ Ġtree . add ( 1 ) ĊĠĠĠĠĠĠĠ Ġtree . add ( 3 ) ĊĠĠĠĠĠĠĠ Ġtree . add ( 5 ) ĊĠĠĠĠĠĠĠ Ġtree . add ( 7 ) ĊĠĠĠĠĠĠĠ Ġtree . add ( 1 0 ) ĊĠĠĠĠĠĠĠ Ġtree . add ( 2 ) ĊĠĠĠĠĠĠĠ Ġtree . build Bal anced Tree () ĊĠĠĠĠĠĠĠ Ġval Ġexpected Ġ= ĠlistOf ( 2 , Ġ 1 , Ġ 5 , Ġ 1 0 , Ġ 7 , Ġ 3 ) ĊĠĠĠĠĠĠĠ ĠassertThat ( tree . post order ()). isEqualTo ( expected ) ĊĠĠĠ Ġ} Ċ }