Assignment: #BST Due: 05/05/02019 Points: 6

Specification

Implemented the TBI (To Be Implemented) methods defined in BST.java.

   (0) implement the preOrderTraversal() method

   (1) implement the postOrderTraversal() method

   (2) implement the levelOrderTraversal() method
       [see code for the algorithm]

   (3) implement the find() method

   (4) implement the min() and max() methods

   (5) implement the delete() method

Submitted programs will be executed using the main() method given in BST.java. The output of your program should match the following. {output file}

inputs: 30 20 40 18 25 24 27 23 21 22 29 35 42 
   30 (root node) left: 20; right: 40; A
   20 (parent: 30) left: 18; right: 25; B
   18 (parent: 20) left: na; right: na; D
   25 (parent: 20) left: 24; right: 27; E
   24 (parent: 25) left: 23; right: na; F
   23 (parent: 24) left: 21; right: na; H
   21 (parent: 23) left: na; right: 22; I
   22 (parent: 21) left: na; right: na; J
   27 (parent: 25) left: na; right: 29; G
   29 (parent: 27) left: na; right: na; K
   40 (parent: 30) left: 35; right: 42; C
   35 (parent: 40) left: na; right: na; L
   42 (parent: 40) left: na; right: na; M

delete(30)...
   35 (root node) left: 20; right: 40; L
   20 (parent: 35) left: 18; right: 25; B
   18 (parent: 20) left: na; right: na; D
   25 (parent: 20) left: 24; right: 27; E
   24 (parent: 25) left: 23; right: na; F
   23 (parent: 24) left: 21; right: na; H
   21 (parent: 23) left: na; right: 22; I
   22 (parent: 21) left: na; right: na; J
   27 (parent: 25) left: na; right: 29; G
   29 (parent: 27) left: na; right: na; K
   40 (parent: 35) left: na; right: 42; C
   42 (parent: 40) left: na; right: na; M

inputs: 30 20 40 18 25 24 27 23 21 22 29 35 42 
   30 (root node) left: 20; right: 40; A
   20 (parent: 30) left: 18; right: 25; B
   18 (parent: 20) left: na; right: na; D
   25 (parent: 20) left: 24; right: 27; E
   24 (parent: 25) left: 23; right: na; F
   23 (parent: 24) left: 21; right: na; H
   21 (parent: 23) left: na; right: 22; I
   22 (parent: 21) left: na; right: na; J
   27 (parent: 25) left: na; right: 29; G
   29 (parent: 27) left: na; right: na; K
   40 (parent: 30) left: 35; right: 42; C
   35 (parent: 40) left: na; right: na; L
   42 (parent: 40) left: na; right: na; M

delete(20)...
   30 (root node) left: 21; right: 40; A
   21 (parent: 30) left: 18; right: 25; I
   18 (parent: 21) left: na; right: na; D
   25 (parent: 21) left: 24; right: 27; E
   24 (parent: 25) left: 23; right: na; F
   23 (parent: 24) left: 22; right: na; H
   22 (parent: 23) left: na; right: na; J
   27 (parent: 25) left: na; right: 29; G
   29 (parent: 27) left: na; right: na; K
   40 (parent: 30) left: 35; right: 42; C
   35 (parent: 40) left: na; right: na; L
   42 (parent: 40) left: na; right: na; M

inputs: 30 20 40 18 25 24 27 23 21 22 29 35 42 
   30 (root node) left: 20; right: 40; A
   20 (parent: 30) left: 18; right: 25; B
   18 (parent: 20) left: na; right: na; D
   25 (parent: 20) left: 24; right: 27; E
   24 (parent: 25) left: 23; right: na; F
   23 (parent: 24) left: 21; right: na; H
   21 (parent: 23) left: na; right: 22; I
   22 (parent: 21) left: na; right: na; J
   27 (parent: 25) left: na; right: 29; G
   29 (parent: 27) left: na; right: na; K
   40 (parent: 30) left: 35; right: 42; C
   35 (parent: 40) left: na; right: na; L
   42 (parent: 40) left: na; right: na; M

delete(40)...
   30 (root node) left: 20; right: 42; A
   20 (parent: 30) left: 18; right: 25; B
   18 (parent: 20) left: na; right: na; D
   25 (parent: 20) left: 24; right: 27; E
   24 (parent: 25) left: 23; right: na; F
   23 (parent: 24) left: 21; right: na; H
   21 (parent: 23) left: na; right: 22; I
   22 (parent: 21) left: na; right: na; J
   27 (parent: 25) left: na; right: 29; G
   29 (parent: 27) left: na; right: na; K
   42 (parent: 30) left: 35; right: na; M
   35 (parent: 42) left: na; right: na; L

inputs: 30 20 40 18 25 24 27 23 21 22 29 35 42 
   30 (root node) left: 20; right: 40; A
   20 (parent: 30) left: 18; right: 25; B
   18 (parent: 20) left: na; right: na; D
   25 (parent: 20) left: 24; right: 27; E
   24 (parent: 25) left: 23; right: na; F
   23 (parent: 24) left: 21; right: na; H
   21 (parent: 23) left: na; right: 22; I
   22 (parent: 21) left: na; right: na; J
   27 (parent: 25) left: na; right: 29; G
   29 (parent: 27) left: na; right: na; K
   40 (parent: 30) left: 35; right: 42; C
   35 (parent: 40) left: na; right: na; L
   42 (parent: 40) left: na; right: na; M

delete(18)...
   30 (root node) left: 20; right: 40; A
   20 (parent: 30) left: na; right: 25; B
   25 (parent: 20) left: 24; right: 27; E
   24 (parent: 25) left: 23; right: na; F
   23 (parent: 24) left: 21; right: na; H
   21 (parent: 23) left: na; right: 22; I
   22 (parent: 21) left: na; right: na; J
   27 (parent: 25) left: na; right: 29; G
   29 (parent: 27) left: na; right: na; K
   40 (parent: 30) left: 35; right: 42; C
   35 (parent: 40) left: na; right: na; L
   42 (parent: 40) left: na; right: na; M

inputs: 30 20 40 18 25 24 27 23 21 22 29 35 42 
   30 (root node) left: 20; right: 40; A
   20 (parent: 30) left: 18; right: 25; B
   18 (parent: 20) left: na; right: na; D
   25 (parent: 20) left: 24; right: 27; E
   24 (parent: 25) left: 23; right: na; F
   23 (parent: 24) left: 21; right: na; H
   21 (parent: 23) left: na; right: 22; I
   22 (parent: 21) left: na; right: na; J
   27 (parent: 25) left: na; right: 29; G
   29 (parent: 27) left: na; right: na; K
   40 (parent: 30) left: 35; right: 42; C
   35 (parent: 40) left: na; right: na; L
   42 (parent: 40) left: na; right: na; M

delete(25)...
   30 (root node) left: 20; right: 40; A
   20 (parent: 30) left: 18; right: 27; B
   18 (parent: 20) left: na; right: na; D
   27 (parent: 20) left: 24; right: 29; G
   24 (parent: 27) left: 23; right: na; F
   23 (parent: 24) left: 21; right: na; H
   21 (parent: 23) left: na; right: 22; I
   22 (parent: 21) left: na; right: na; J
   29 (parent: 27) left: na; right: na; K
   40 (parent: 30) left: 35; right: 42; C
   35 (parent: 40) left: na; right: na; L
   42 (parent: 40) left: na; right: na; M

inputs: 30 20 40 18 25 24 27 23 21 22 29 35 42 
   30 (root node) left: 20; right: 40; A
   20 (parent: 30) left: 18; right: 25; B
   18 (parent: 20) left: na; right: na; D
   25 (parent: 20) left: 24; right: 27; E
   24 (parent: 25) left: 23; right: na; F
   23 (parent: 24) left: 21; right: na; H
   21 (parent: 23) left: na; right: 22; I
   22 (parent: 21) left: na; right: na; J
   27 (parent: 25) left: na; right: 29; G
   29 (parent: 27) left: na; right: na; K
   40 (parent: 30) left: 35; right: 42; C
   35 (parent: 40) left: na; right: na; L
   42 (parent: 40) left: na; right: na; M

delete(24)...
   30 (root node) left: 20; right: 40; A
   20 (parent: 30) left: 18; right: 25; B
   18 (parent: 20) left: na; right: na; D
   25 (parent: 20) left: 23; right: 27; E
   23 (parent: 25) left: 21; right: na; H
   21 (parent: 23) left: na; right: 22; I
   22 (parent: 21) left: na; right: na; J
   27 (parent: 25) left: na; right: 29; G
   29 (parent: 27) left: na; right: na; K
   40 (parent: 30) left: 35; right: 42; C
   35 (parent: 40) left: na; right: na; L
   42 (parent: 40) left: na; right: na; M

inputs: 30 20 40 18 25 24 27 23 21 22 29 35 42 
   30 (root node) left: 20; right: 40; A
   20 (parent: 30) left: 18; right: 25; B
   18 (parent: 20) left: na; right: na; D
   25 (parent: 20) left: 24; right: 27; E
   24 (parent: 25) left: 23; right: na; F
   23 (parent: 24) left: 21; right: na; H
   21 (parent: 23) left: na; right: 22; I
   22 (parent: 21) left: na; right: na; J
   27 (parent: 25) left: na; right: 29; G
   29 (parent: 27) left: na; right: na; K
   40 (parent: 30) left: 35; right: 42; C
   35 (parent: 40) left: na; right: na; L
   42 (parent: 40) left: na; right: na; M

delete(27)...
   30 (root node) left: 20; right: 40; A
   20 (parent: 30) left: 18; right: 25; B
   18 (parent: 20) left: na; right: na; D
   25 (parent: 20) left: 24; right: 29; E
   24 (parent: 25) left: 23; right: na; F
   23 (parent: 24) left: 21; right: na; H
   21 (parent: 23) left: na; right: 22; I
   22 (parent: 21) left: na; right: na; J
   29 (parent: 25) left: na; right: na; K
   40 (parent: 30) left: 35; right: 42; C
   35 (parent: 40) left: na; right: na; L
   42 (parent: 40) left: na; right: na; M

inputs: 30 20 40 18 25 24 27 23 21 22 29 35 42 
   30 (root node) left: 20; right: 40; A
   20 (parent: 30) left: 18; right: 25; B
   18 (parent: 20) left: na; right: na; D
   25 (parent: 20) left: 24; right: 27; E
   24 (parent: 25) left: 23; right: na; F
   23 (parent: 24) left: 21; right: na; H
   21 (parent: 23) left: na; right: 22; I
   22 (parent: 21) left: na; right: na; J
   27 (parent: 25) left: na; right: 29; G
   29 (parent: 27) left: na; right: na; K
   40 (parent: 30) left: 35; right: 42; C
   35 (parent: 40) left: na; right: na; L
   42 (parent: 40) left: na; right: na; M

delete(23)...
   30 (root node) left: 20; right: 40; A
   20 (parent: 30) left: 18; right: 25; B
   18 (parent: 20) left: na; right: na; D
   25 (parent: 20) left: 24; right: 27; E
   24 (parent: 25) left: 21; right: na; F
   21 (parent: 24) left: na; right: 22; I
   22 (parent: 21) left: na; right: na; J
   27 (parent: 25) left: na; right: 29; G
   29 (parent: 27) left: na; right: na; K
   40 (parent: 30) left: 35; right: 42; C
   35 (parent: 40) left: na; right: na; L
   42 (parent: 40) left: na; right: na; M

inputs: 30 20 40 18 25 24 27 23 21 22 29 35 42 
   30 (root node) left: 20; right: 40; A
   20 (parent: 30) left: 18; right: 25; B
   18 (parent: 20) left: na; right: na; D
   25 (parent: 20) left: 24; right: 27; E
   24 (parent: 25) left: 23; right: na; F
   23 (parent: 24) left: 21; right: na; H
   21 (parent: 23) left: na; right: 22; I
   22 (parent: 21) left: na; right: na; J
   27 (parent: 25) left: na; right: 29; G
   29 (parent: 27) left: na; right: na; K
   40 (parent: 30) left: 35; right: 42; C
   35 (parent: 40) left: na; right: na; L
   42 (parent: 40) left: na; right: na; M

delete(21)...
   30 (root node) left: 20; right: 40; A
   20 (parent: 30) left: 18; right: 25; B
   18 (parent: 20) left: na; right: na; D
   25 (parent: 20) left: 24; right: 27; E
   24 (parent: 25) left: 23; right: na; F
   23 (parent: 24) left: 22; right: na; H
   22 (parent: 23) left: na; right: na; J
   27 (parent: 25) left: na; right: 29; G
   29 (parent: 27) left: na; right: na; K
   40 (parent: 30) left: 35; right: 42; C
   35 (parent: 40) left: na; right: na; L
   42 (parent: 40) left: na; right: na; M

inputs: 30 20 40 18 25 24 27 23 21 22 29 35 42 
   30 (root node) left: 20; right: 40; A
   20 (parent: 30) left: 18; right: 25; B
   18 (parent: 20) left: na; right: na; D
   25 (parent: 20) left: 24; right: 27; E
   24 (parent: 25) left: 23; right: na; F
   23 (parent: 24) left: 21; right: na; H
   21 (parent: 23) left: na; right: 22; I
   22 (parent: 21) left: na; right: na; J
   27 (parent: 25) left: na; right: 29; G
   29 (parent: 27) left: na; right: na; K
   40 (parent: 30) left: 35; right: 42; C
   35 (parent: 40) left: na; right: na; L
   42 (parent: 40) left: na; right: na; M

delete(22)...
   30 (root node) left: 20; right: 40; A
   20 (parent: 30) left: 18; right: 25; B
   18 (parent: 20) left: na; right: na; D
   25 (parent: 20) left: 24; right: 27; E
   24 (parent: 25) left: 23; right: na; F
   23 (parent: 24) left: 21; right: na; H
   21 (parent: 23) left: na; right: na; I
   27 (parent: 25) left: na; right: 29; G
   29 (parent: 27) left: na; right: na; K
   40 (parent: 30) left: 35; right: 42; C
   35 (parent: 40) left: na; right: na; L
   42 (parent: 40) left: na; right: na; M

inputs: 30 20 40 18 25 24 27 23 21 22 29 35 42 
   30 (root node) left: 20; right: 40; A
   20 (parent: 30) left: 18; right: 25; B
   18 (parent: 20) left: na; right: na; D
   25 (parent: 20) left: 24; right: 27; E
   24 (parent: 25) left: 23; right: na; F
   23 (parent: 24) left: 21; right: na; H
   21 (parent: 23) left: na; right: 22; I
   22 (parent: 21) left: na; right: na; J
   27 (parent: 25) left: na; right: 29; G
   29 (parent: 27) left: na; right: na; K
   40 (parent: 30) left: 35; right: 42; C
   35 (parent: 40) left: na; right: na; L
   42 (parent: 40) left: na; right: na; M

delete(29)...
   30 (root node) left: 20; right: 40; A
   20 (parent: 30) left: 18; right: 25; B
   18 (parent: 20) left: na; right: na; D
   25 (parent: 20) left: 24; right: 27; E
   24 (parent: 25) left: 23; right: na; F
   23 (parent: 24) left: 21; right: na; H
   21 (parent: 23) left: na; right: 22; I
   22 (parent: 21) left: na; right: na; J
   27 (parent: 25) left: na; right: na; G
   40 (parent: 30) left: 35; right: 42; C
   35 (parent: 40) left: na; right: na; L
   42 (parent: 40) left: na; right: na; M

inputs: 30 20 40 18 25 24 27 23 21 22 29 35 42 
   30 (root node) left: 20; right: 40; A
   20 (parent: 30) left: 18; right: 25; B
   18 (parent: 20) left: na; right: na; D
   25 (parent: 20) left: 24; right: 27; E
   24 (parent: 25) left: 23; right: na; F
   23 (parent: 24) left: 21; right: na; H
   21 (parent: 23) left: na; right: 22; I
   22 (parent: 21) left: na; right: na; J
   27 (parent: 25) left: na; right: 29; G
   29 (parent: 27) left: na; right: na; K
   40 (parent: 30) left: 35; right: 42; C
   35 (parent: 40) left: na; right: na; L
   42 (parent: 40) left: na; right: na; M

delete(35)...
   30 (root node) left: 20; right: 40; A
   20 (parent: 30) left: 18; right: 25; B
   18 (parent: 20) left: na; right: na; D
   25 (parent: 20) left: 24; right: 27; E
   24 (parent: 25) left: 23; right: na; F
   23 (parent: 24) left: 21; right: na; H
   21 (parent: 23) left: na; right: 22; I
   22 (parent: 21) left: na; right: na; J
   27 (parent: 25) left: na; right: 29; G
   29 (parent: 27) left: na; right: na; K
   40 (parent: 30) left: na; right: 42; C
   42 (parent: 40) left: na; right: na; M

inputs: 30 20 40 18 25 24 27 23 21 22 29 35 42 
   30 (root node) left: 20; right: 40; A
   20 (parent: 30) left: 18; right: 25; B
   18 (parent: 20) left: na; right: na; D
   25 (parent: 20) left: 24; right: 27; E
   24 (parent: 25) left: 23; right: na; F
   23 (parent: 24) left: 21; right: na; H
   21 (parent: 23) left: na; right: 22; I
   22 (parent: 21) left: na; right: na; J
   27 (parent: 25) left: na; right: 29; G
   29 (parent: 27) left: na; right: na; K
   40 (parent: 30) left: 35; right: 42; C
   35 (parent: 40) left: na; right: na; L
   42 (parent: 40) left: na; right: na; M

delete(42)...
   30 (root node) left: 20; right: 40; A
   20 (parent: 30) left: 18; right: 25; B
   18 (parent: 20) left: na; right: na; D
   25 (parent: 20) left: 24; right: 27; E
   24 (parent: 25) left: 23; right: na; F
   23 (parent: 24) left: 21; right: na; H
   21 (parent: 23) left: na; right: 22; I
   22 (parent: 21) left: na; right: na; J
   27 (parent: 25) left: na; right: 29; G
   29 (parent: 27) left: na; right: na; K
   40 (parent: 30) left: 35; right: na; C
   35 (parent: 40) left: na; right: na; L

inputs: 30 20 40 18 25 24 27 23 21 22 29 35 42 
min = 18; max = 42
find(30): found
find(42): found
find(205): not found
find(27): found

level-order traversal:
   30 (root node) left: 20; right: 40; A
   20 (parent: 30) left: 18; right: 25; B
   40 (parent: 30) left: 35; right: 42; C
   18 (parent: 20) left: na; right: na; D
   25 (parent: 20) left: 24; right: 27; E
   35 (parent: 40) left: na; right: na; L
   42 (parent: 40) left: na; right: na; M
   24 (parent: 25) left: 23; right: na; F
   27 (parent: 25) left: na; right: 29; G
   23 (parent: 24) left: 21; right: na; H
   29 (parent: 27) left: na; right: na; K
   21 (parent: 23) left: na; right: 22; I
   22 (parent: 21) left: na; right: na; J

inputs: 10
   10 (root node) left: na; right: na; A

delete(10)...
   empty tree (no traversal)

inputs: 10 5
   5 (parent: 10) left: na; right: na; B
   10 (root node) left: 5; right: na; A

delete(10)...
   5 (root node) left: na; right: na; B

inputs: 10 15
   10 (root node) left: na; right: 15; A
   15 (parent: 10) left: na; right: na; B

delete(10)...
   15 (root node) left: na; right: na; B

inputs: 10 15 5
   5 (parent: 10) left: na; right: na; C
   10 (root node) left: 5; right: 15; A
   15 (parent: 10) left: na; right: na; B

delete(10)...
   5 (parent: 15) left: na; right: na; C
   15 (root node) left: 5; right: na; B