Assignment: #BST Due: 05/11/2017 Points: 6

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.


inputs: 30 20 40 18 25 24 27 23 21 22 29 35 42 
   30 (root  node) left: 20; right: 40
   20 (parent: 30) left: 18; right: 25
   18 (parent: 20) left: na; right: na
   25 (parent: 20) left: 24; right: 27
   24 (parent: 25) left: 23; right: na
   23 (parent: 24) left: 21; right: na
   21 (parent: 23) left: na; right: 22
   22 (parent: 21) left: na; right: na
   27 (parent: 25) left: na; right: 29
   29 (parent: 27) left: na; right: na
   40 (parent: 30) left: 35; right: 42
   35 (parent: 40) left: na; right: na
   42 (parent: 40) left: na; right: na

delete(30)...
   35 (root  node) left: 20; right: 40
   20 (parent: 35) left: 18; right: 25
   18 (parent: 20) left: na; right: na
   25 (parent: 20) left: 24; right: 27
   24 (parent: 25) left: 23; right: na
   23 (parent: 24) left: 21; right: na
   21 (parent: 23) left: na; right: 22
   22 (parent: 21) left: na; right: na
   27 (parent: 25) left: na; right: 29
   29 (parent: 27) left: na; right: na
   40 (parent: 35) left: na; right: 42
   42 (parent: 40) left: na; right: na

inputs: 30 20 40 18 25 24 27 23 21 22 29 35 42 
   30 (root  node) left: 20; right: 40
   20 (parent: 30) left: 18; right: 25
   18 (parent: 20) left: na; right: na
   25 (parent: 20) left: 24; right: 27
   24 (parent: 25) left: 23; right: na
   23 (parent: 24) left: 21; right: na
   21 (parent: 23) left: na; right: 22
   22 (parent: 21) left: na; right: na
   27 (parent: 25) left: na; right: 29
   29 (parent: 27) left: na; right: na
   40 (parent: 30) left: 35; right: 42
   35 (parent: 40) left: na; right: na
   42 (parent: 40) left: na; right: na

delete(20)...
   30 (root  node) left: 21; right: 40
   21 (parent: 30) left: 18; right: 25
   18 (parent: 21) left: na; right: na
   25 (parent: 21) left: 24; right: 27
   24 (parent: 25) left: 23; right: na
   23 (parent: 24) left: 22; right: na
   22 (parent: 23) left: na; right: na
   27 (parent: 25) left: na; right: 29
   29 (parent: 27) left: na; right: na
   40 (parent: 30) left: 35; right: 42
   35 (parent: 40) left: na; right: na
   42 (parent: 40) left: na; right: na

inputs: 30 20 40 18 25 24 27 23 21 22 29 35 42 
   30 (root  node) left: 20; right: 40
   20 (parent: 30) left: 18; right: 25
   18 (parent: 20) left: na; right: na
   25 (parent: 20) left: 24; right: 27
   24 (parent: 25) left: 23; right: na
   23 (parent: 24) left: 21; right: na
   21 (parent: 23) left: na; right: 22
   22 (parent: 21) left: na; right: na
   27 (parent: 25) left: na; right: 29
   29 (parent: 27) left: na; right: na
   40 (parent: 30) left: 35; right: 42
   35 (parent: 40) left: na; right: na
   42 (parent: 40) left: na; right: na

delete(40)...
   30 (root  node) left: 20; right: 42
   20 (parent: 30) left: 18; right: 25
   18 (parent: 20) left: na; right: na
   25 (parent: 20) left: 24; right: 27
   24 (parent: 25) left: 23; right: na
   23 (parent: 24) left: 21; right: na
   21 (parent: 23) left: na; right: 22
   22 (parent: 21) left: na; right: na
   27 (parent: 25) left: na; right: 29
   29 (parent: 27) left: na; right: na
   42 (parent: 30) left: 35; right: na
   35 (parent: 42) left: na; right: na

inputs: 30 20 40 18 25 24 27 23 21 22 29 35 42 
   30 (root  node) left: 20; right: 40
   20 (parent: 30) left: 18; right: 25
   18 (parent: 20) left: na; right: na
   25 (parent: 20) left: 24; right: 27
   24 (parent: 25) left: 23; right: na
   23 (parent: 24) left: 21; right: na
   21 (parent: 23) left: na; right: 22
   22 (parent: 21) left: na; right: na
   27 (parent: 25) left: na; right: 29
   29 (parent: 27) left: na; right: na
   40 (parent: 30) left: 35; right: 42
   35 (parent: 40) left: na; right: na
   42 (parent: 40) left: na; right: na

delete(18)...
   30 (root  node) left: 20; right: 40
   20 (parent: 30) left: na; right: 25
   25 (parent: 20) left: 24; right: 27
   24 (parent: 25) left: 23; right: na
   23 (parent: 24) left: 21; right: na
   21 (parent: 23) left: na; right: 22
   22 (parent: 21) left: na; right: na
   27 (parent: 25) left: na; right: 29
   29 (parent: 27) left: na; right: na
   40 (parent: 30) left: 35; right: 42
   35 (parent: 40) left: na; right: na
   42 (parent: 40) left: na; right: na

inputs: 30 20 40 18 25 24 27 23 21 22 29 35 42 
   30 (root  node) left: 20; right: 40
   20 (parent: 30) left: 18; right: 25
   18 (parent: 20) left: na; right: na
   25 (parent: 20) left: 24; right: 27
   24 (parent: 25) left: 23; right: na
   23 (parent: 24) left: 21; right: na
   21 (parent: 23) left: na; right: 22
   22 (parent: 21) left: na; right: na
   27 (parent: 25) left: na; right: 29
   29 (parent: 27) left: na; right: na
   40 (parent: 30) left: 35; right: 42
   35 (parent: 40) left: na; right: na
   42 (parent: 40) left: na; right: na

delete(25)...
   30 (root  node) left: 20; right: 40
   20 (parent: 30) left: 18; right: 27
   18 (parent: 20) left: na; right: na
   27 (parent: 20) left: 24; right: 29
   24 (parent: 27) left: 23; right: na
   23 (parent: 24) left: 21; right: na
   21 (parent: 23) left: na; right: 22
   22 (parent: 21) left: na; right: na
   29 (parent: 27) left: na; right: na
   40 (parent: 30) left: 35; right: 42
   35 (parent: 40) left: na; right: na
   42 (parent: 40) left: na; right: na

inputs: 30 20 40 18 25 24 27 23 21 22 29 35 42 
   30 (root  node) left: 20; right: 40
   20 (parent: 30) left: 18; right: 25
   18 (parent: 20) left: na; right: na
   25 (parent: 20) left: 24; right: 27
   24 (parent: 25) left: 23; right: na
   23 (parent: 24) left: 21; right: na
   21 (parent: 23) left: na; right: 22
   22 (parent: 21) left: na; right: na
   27 (parent: 25) left: na; right: 29
   29 (parent: 27) left: na; right: na
   40 (parent: 30) left: 35; right: 42
   35 (parent: 40) left: na; right: na
   42 (parent: 40) left: na; right: na

delete(24)...
   30 (root  node) left: 20; right: 40
   20 (parent: 30) left: 18; right: 25
   18 (parent: 20) left: na; right: na
   25 (parent: 20) left: 23; right: 27
   23 (parent: 25) left: 21; right: na
   21 (parent: 23) left: na; right: 22
   22 (parent: 21) left: na; right: na
   27 (parent: 25) left: na; right: 29
   29 (parent: 27) left: na; right: na
   40 (parent: 30) left: 35; right: 42
   35 (parent: 40) left: na; right: na
   42 (parent: 40) left: na; right: na

inputs: 30 20 40 18 25 24 27 23 21 22 29 35 42 
   30 (root  node) left: 20; right: 40
   20 (parent: 30) left: 18; right: 25
   18 (parent: 20) left: na; right: na
   25 (parent: 20) left: 24; right: 27
   24 (parent: 25) left: 23; right: na
   23 (parent: 24) left: 21; right: na
   21 (parent: 23) left: na; right: 22
   22 (parent: 21) left: na; right: na
   27 (parent: 25) left: na; right: 29
   29 (parent: 27) left: na; right: na
   40 (parent: 30) left: 35; right: 42
   35 (parent: 40) left: na; right: na
   42 (parent: 40) left: na; right: na

delete(27)...
   30 (root  node) left: 20; right: 40
   20 (parent: 30) left: 18; right: 25
   18 (parent: 20) left: na; right: na
   25 (parent: 20) left: 24; right: 29
   24 (parent: 25) left: 23; right: na
   23 (parent: 24) left: 21; right: na
   21 (parent: 23) left: na; right: 22
   22 (parent: 21) left: na; right: na
   29 (parent: 25) left: na; right: na
   40 (parent: 30) left: 35; right: 42
   35 (parent: 40) left: na; right: na
   42 (parent: 40) left: na; right: na

inputs: 30 20 40 18 25 24 27 23 21 22 29 35 42 
   30 (root  node) left: 20; right: 40
   20 (parent: 30) left: 18; right: 25
   18 (parent: 20) left: na; right: na
   25 (parent: 20) left: 24; right: 27
   24 (parent: 25) left: 23; right: na
   23 (parent: 24) left: 21; right: na
   21 (parent: 23) left: na; right: 22
   22 (parent: 21) left: na; right: na
   27 (parent: 25) left: na; right: 29
   29 (parent: 27) left: na; right: na
   40 (parent: 30) left: 35; right: 42
   35 (parent: 40) left: na; right: na
   42 (parent: 40) left: na; right: na

delete(23)...
   30 (root  node) left: 20; right: 40
   20 (parent: 30) left: 18; right: 25
   18 (parent: 20) left: na; right: na
   25 (parent: 20) left: 24; right: 27
   24 (parent: 25) left: 21; right: na
   21 (parent: 24) left: na; right: 22
   22 (parent: 21) left: na; right: na
   27 (parent: 25) left: na; right: 29
   29 (parent: 27) left: na; right: na
   40 (parent: 30) left: 35; right: 42
   35 (parent: 40) left: na; right: na
   42 (parent: 40) left: na; right: na

inputs: 30 20 40 18 25 24 27 23 21 22 29 35 42 
   30 (root  node) left: 20; right: 40
   20 (parent: 30) left: 18; right: 25
   18 (parent: 20) left: na; right: na
   25 (parent: 20) left: 24; right: 27
   24 (parent: 25) left: 23; right: na
   23 (parent: 24) left: 21; right: na
   21 (parent: 23) left: na; right: 22
   22 (parent: 21) left: na; right: na
   27 (parent: 25) left: na; right: 29
   29 (parent: 27) left: na; right: na
   40 (parent: 30) left: 35; right: 42
   35 (parent: 40) left: na; right: na
   42 (parent: 40) left: na; right: na

delete(21)...
   30 (root  node) left: 20; right: 40
   20 (parent: 30) left: 18; right: 25
   18 (parent: 20) left: na; right: na
   25 (parent: 20) left: 24; right: 27
   24 (parent: 25) left: 23; right: na
   23 (parent: 24) left: 22; right: na
   22 (parent: 23) left: na; right: na
   27 (parent: 25) left: na; right: 29
   29 (parent: 27) left: na; right: na
   40 (parent: 30) left: 35; right: 42
   35 (parent: 40) left: na; right: na
   42 (parent: 40) left: na; right: na

inputs: 30 20 40 18 25 24 27 23 21 22 29 35 42 
   30 (root  node) left: 20; right: 40
   20 (parent: 30) left: 18; right: 25
   18 (parent: 20) left: na; right: na
   25 (parent: 20) left: 24; right: 27
   24 (parent: 25) left: 23; right: na
   23 (parent: 24) left: 21; right: na
   21 (parent: 23) left: na; right: 22
   22 (parent: 21) left: na; right: na
   27 (parent: 25) left: na; right: 29
   29 (parent: 27) left: na; right: na
   40 (parent: 30) left: 35; right: 42
   35 (parent: 40) left: na; right: na
   42 (parent: 40) left: na; right: na

delete(22)...
   30 (root  node) left: 20; right: 40
   20 (parent: 30) left: 18; right: 25
   18 (parent: 20) left: na; right: na
   25 (parent: 20) left: 24; right: 27
   24 (parent: 25) left: 23; right: na
   23 (parent: 24) left: 21; right: na
   21 (parent: 23) left: na; right: na
   27 (parent: 25) left: na; right: 29
   29 (parent: 27) left: na; right: na
   40 (parent: 30) left: 35; right: 42
   35 (parent: 40) left: na; right: na
   42 (parent: 40) left: na; right: na

inputs: 30 20 40 18 25 24 27 23 21 22 29 35 42 
   30 (root  node) left: 20; right: 40
   20 (parent: 30) left: 18; right: 25
   18 (parent: 20) left: na; right: na
   25 (parent: 20) left: 24; right: 27
   24 (parent: 25) left: 23; right: na
   23 (parent: 24) left: 21; right: na
   21 (parent: 23) left: na; right: 22
   22 (parent: 21) left: na; right: na
   27 (parent: 25) left: na; right: 29
   29 (parent: 27) left: na; right: na
   40 (parent: 30) left: 35; right: 42
   35 (parent: 40) left: na; right: na
   42 (parent: 40) left: na; right: na

delete(29)...
   30 (root  node) left: 20; right: 40
   20 (parent: 30) left: 18; right: 25
   18 (parent: 20) left: na; right: na
   25 (parent: 20) left: 24; right: 27
   24 (parent: 25) left: 23; right: na
   23 (parent: 24) left: 21; right: na
   21 (parent: 23) left: na; right: 22
   22 (parent: 21) left: na; right: na
   27 (parent: 25) left: na; right: na
   40 (parent: 30) left: 35; right: 42
   35 (parent: 40) left: na; right: na
   42 (parent: 40) left: na; right: na

inputs: 30 20 40 18 25 24 27 23 21 22 29 35 42 
   30 (root  node) left: 20; right: 40
   20 (parent: 30) left: 18; right: 25
   18 (parent: 20) left: na; right: na
   25 (parent: 20) left: 24; right: 27
   24 (parent: 25) left: 23; right: na
   23 (parent: 24) left: 21; right: na
   21 (parent: 23) left: na; right: 22
   22 (parent: 21) left: na; right: na
   27 (parent: 25) left: na; right: 29
   29 (parent: 27) left: na; right: na
   40 (parent: 30) left: 35; right: 42
   35 (parent: 40) left: na; right: na
   42 (parent: 40) left: na; right: na

delete(35)...
   30 (root  node) left: 20; right: 40
   20 (parent: 30) left: 18; right: 25
   18 (parent: 20) left: na; right: na
   25 (parent: 20) left: 24; right: 27
   24 (parent: 25) left: 23; right: na
   23 (parent: 24) left: 21; right: na
   21 (parent: 23) left: na; right: 22
   22 (parent: 21) left: na; right: na
   27 (parent: 25) left: na; right: 29
   29 (parent: 27) left: na; right: na
   40 (parent: 30) left: na; right: 42
   42 (parent: 40) left: na; right: na

inputs: 30 20 40 18 25 24 27 23 21 22 29 35 42 
   30 (root  node) left: 20; right: 40
   20 (parent: 30) left: 18; right: 25
   18 (parent: 20) left: na; right: na
   25 (parent: 20) left: 24; right: 27
   24 (parent: 25) left: 23; right: na
   23 (parent: 24) left: 21; right: na
   21 (parent: 23) left: na; right: 22
   22 (parent: 21) left: na; right: na
   27 (parent: 25) left: na; right: 29
   29 (parent: 27) left: na; right: na
   40 (parent: 30) left: 35; right: 42
   35 (parent: 40) left: na; right: na
   42 (parent: 40) left: na; right: na

delete(42)...
   30 (root  node) left: 20; right: 40
   20 (parent: 30) left: 18; right: 25
   18 (parent: 20) left: na; right: na
   25 (parent: 20) left: 24; right: 27
   24 (parent: 25) left: 23; right: na
   23 (parent: 24) left: 21; right: na
   21 (parent: 23) left: na; right: 22
   22 (parent: 21) left: na; right: na
   27 (parent: 25) left: na; right: 29
   29 (parent: 27) left: na; right: na
   40 (parent: 30) left: 35; right: na
   35 (parent: 40) left: na; right: na

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
   20 (parent: 30) left: 18; right: 25
   40 (parent: 30) left: 35; right: 42
   18 (parent: 20) left: na; right: na
   25 (parent: 20) left: 24; right: 27
   35 (parent: 40) left: na; right: na
   42 (parent: 40) left: na; right: na
   24 (parent: 25) left: 23; right: na
   27 (parent: 25) left: na; right: 29
   23 (parent: 24) left: 21; right: na
   29 (parent: 27) left: na; right: na
   21 (parent: 23) left: na; right: 22
   22 (parent: 21) left: na; right: na

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

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

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

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

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

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

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

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