Skip to main content

Section 31.14 Exercises

The exercises in this section use the same logic as our basic binary search tree implementation. Do your best to recreate the functionality without looking at the previous code.
The class declaration looks like this:
Listing 31.14.1. CharBST Class Declaration
class CharBST {
private:
  BSTNode* root;
public:
... functions not shown ...
};
Where BSTNode is defined as:
Listing 31.14.2. BSTNode Declaration
struct BSTNode {
  // Store a value and two child pointers
  char value;
  BSTNode* left;
  BSTNode* right;
};

Checkpoint 31.14.1.

Implement containsIterative for the CharBST class.

Checkpoint 31.14.2.

Implement the recursive helper function for containsRecursive for the CharBST class.

Checkpoint 31.14.3.

Implement the insertIterative for the CharBST class.

Checkpoint 31.14.4.

Implement the recursive helper function for insertRecursive for the CharBST class.

Checkpoint 31.14.5.

Implement copySubTree for the CharBST class. It should create a deep copy of a subtree rooted at the given node and return a pointer to the root of the new subtree.

Checkpoint 31.14.6.

Implement smallestValueFrom for the CharBST class. It should find the smallest value in a subtree rooted at the given node and return it.

Checkpoint 31.14.7.

Implement recursive helper function removeSmallestHelper for the CharBST class. It should find and remove the smallest value in a subtree rooted at the given node and return a pointer to the root of the modified subtree.

Checkpoint 31.14.8.

Finish the implementation of the recursive helper function removeHelper for the CharBST class. It should find and remove the specified value in a subtree rooted at the given node and return a pointer to the root of the modified subtree.
You will likely want your code for smallestValueFrom from Checkpoint 31.14.6.
You have attempted of activities on this page.
PrevTopNext