Assignment: #BST Due: 12/09/02018 Points: 7

Specification

Make the following modifications to the BST.java program.

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

   (1) implement the find() method

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

   (3) 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