BST Insertion

Question 1

What is the first step of a BST insertion?

Answer 1

search for the key you want to insert

Question 2

What are the two cases for BST insertions

Answer 2

1. The tree is empty (the root pointer is null)
2. the tree is not empty

Question 3

What does root look like before and after adding an item to an empty tree?

Answer 3

Question 4

What is the specific code to insert into an empty BST?

Answer 4

Question 5

In general, what do we need to do to insert into a BST that is not empty?

Answer 5

Question 6

In the attached example, where would prev and curr be when inserting 19 into the BST

Answer 6

Question 7

In a BST insertion, after we have determined the correct spot using prev and curr, what is the next step?

How do you determine the appropriate child of prev?

Answer 7

Question 8

Draw the following sequencially:

Insert 15, 8, 12, 19, 5 and 23 into an initially empty BST

Answer 8

Question 9

What is the iterative insert code if the BST is NOT empty(after the initial else condition)

Answer 9

Question 10

In the BST class, what is the code for the recursive public driver method for insert?

Answer 10

Question 11

In the Node class, what is the code for the recursive helper method?

Answer 11

Question 12

Draw the table diagram of adding 20 into the following recursive insertion method for a BST

Answer 12