16.3. Recursive Insert Case

Try these first

1. 1.

   What should you do if you want to insert a value into an empty search tree?

   Hint

   Think about what the starting point of a tree might be.

2. 2.

   Can you insert a duplicate value into a search tree?

   Hint

   Consider how duplicates might affect order.

3. 3.

   What should you do when inserting a value that is already present in the tree?

   • Insert it again
   • Ignore the insertion
   • Replace the existing value

   Hint

   Think about how a duplicate might affect the tree structure.

4. 4.

   True or False: Inserting into an empty search tree requires creating a new root node.

   • True
   • False

   Hint

   Consider the definition of what a tree's root is.

5. 5.

   Given the following tree with values [15, 10, 20, 8, 12, 18, 25], what will it look like after inserting the value 17?

   Hint

   Draw the tree and visualize the path driven by comparisons.

6. 6.

   If you have a skewed tree where every node only has a right child, what would the structure look like after inserting the value that should be its left child?

   Hint

   Consider how balancing might take effect in real scenarios.