Data Structures, Algorithms, & Applications in C++
Chapter 14, Exercise 7

(a)

The tree following each insert is:

10          10              10                 10
           /               /  \               /  \
           5              5    20            5    20
                                                 /
                                                14



      10
     /  \
    5    20
        /  \
       14  30



      10
     /  \
    5    20
     \  /  \
     8 14  30


      10
     /  \
    5    20
     \  /  \
     8 14  30
    /
   6

      10
     /  \
    5    20
     \  /  \
     8 14  30
    / \
   6   9

      10
     /  \
    5    20
     \  /  \
     8 14  30
    / \      \
   6   9     35


      10
     /  \
    5    20
     \  /  \
     8 14  30
    / \   /  \
   6   9 25  35


      10
     /  \
    5    20
  /  \  /  \
 3   8 14  30
    / \   /  \
   6   9 25  35


             10
           /   \
         /      \
       /         \
      /           \
     5            20
   /  \          /  \
  /    \        /    \
 /      \      /      \
 3      8     14      30
       / \   /       /  \
      6   9 12      25  35


             10
           /   \
         /      \
       /         \
      /           \
     5            20
   /  \          /  \
  /    \        /    \
 /      \      /      \
 3      8     14      30
       / \   /  \    /  \
      6   9 12  17  25  35

(b)

After 35 is removed, the tree is:

             10
           /   \
         /      \
       /         \
      /           \
     5            20
   /  \          /  \
  /    \        /    \
 /      \      /      \
 3      8     14      30
       / \   /  \    / 
      6   9 12  17  25  

Following the removal of 30, the tree is:

             10
           /   \
         /      \
       /         \
      /           \
     5            20
   /  \          /  \
  /    \        /    \
 /      \      /      \
 3      8     14      25
       / \   /  \
      6   9 12  17

Removing 20 gives us the tree:

             10
           /   \
         /      \
       /         \
      /           \
     5            17
   /  \          /  \
  /    \        /    \
 /      \      /      \
 3      8     14      25
       / \   /
      6   9 12

Removing 10 gives us the tree:

             9
           /   \
         /      \
       /         \
      /           \
     5            17
   /  \          /  \
  /    \        /    \
 /      \      /      \
 3      8     14      25
       /     /
      6     12