Description

The purpose of this challenge is to implement a binary search tree.

Requirements – PART 1

Define an int array in main() as below

int values[25] = { 23, 117, 45, 19, 7, 
13, 17, 40, 9, 11, 
93, 49, 35, 8, 3, 
10, 22, 77, 16, 6, 
51, 57, 55, 90, 31 };

Define a node as below

struct Node
{
  int value;
  Node * left;
  Node * right;
};

Create a class BST

class BST
{
  private:
    int count;
    Node * root;
    Node * create(int value);
    void add_node(Node *subtreeroot, int value); 
  public:
    BST() {}
    ~BST() {}
    void add(int item);
    friend void show(BST & bst);
};

In the default constructor for BST, set root to NULL and count to 0
Write a private function Node * create(int value). This function returns the address of a new node (use the new operator to create a new node). Set the node’s value to value. Set both left and right to NULL. Increment the private variable count.
Create a function void add_node(Node * subtreeroot, int value). This function will recursively traverse subtreeroot to correctly place the new value. Using VLR traversal, check that the current node being “visited” is not equivalent to value. If it is, stop the traversal — we only want to add in unique values. Otherwise, this function will create a new node at the appropriate time during traversal and link the new node to the correct parent as appropriate. Set left and right node properties as appropriate as well. Pseudo code is below:
```
if (subtreeroot->value does not equal value) // V
begin
  if (value < subtreeroot->value) // L
    if (subtreeroot->left is NOT NULL)
      call add_node(subtreeroot->left, value);
    else
      set subtreeroot->left to create(value)
  else // R
     if (subtreeroot->right is NOT NULL)
	call add_node(subtreeroot->right, value);
     else
        set subtreeroot->right to create(value)
end
```
In the add() function, call add_node() passing the private root variable into add_node() to start the recursive VLR traversal.
Create a global function void show_node(Node * subtreeroot). This function will recursively traverse subtreeroot and display the value of the nodes, using LVR (in-order) traversal.
Create a friend function in BST to display the contents of the BST. friend void show(BST & bst). This function will call show_node, using LVR traversal.

Create a new function void destroy_node(Node * node). In this function, recursively call node->left, then node->right as long as node is not NULL. This uses an LRV traversal

void destroy_node(Node *node)
{
  if (node != NULL)
  {
    destroy_node(node->left); // L
    destroy_node(node->right); // R
  }
  delete node; // V
  count--;
}

In the class’ destructor, call destroy_node() passing in root to start the traversal.
In main(),
1. Fill up a BST object by adding all the items from the values array, one at a time. Call bst.add() to add each item from the array.
2. Display the contents of the BST using the friend function.
3. Ask the user to enter a new integer value
4. Add this new value into the BST object
5. Display the contents of the BST again using friend function. See that the new value is in the right location.
6. Display the count of nodes in the BST

Requirements – Part 2

In the BST class, add a private function Node * find_node(Node * subtreeroot, int value). This function calls itself recursively in VLR traversal mode looking for value. This function returns NULL if it doesn’t find a matching node. It returns the address of a matching node whose value is value.
In the BST class, add a public function bool find(int value). This function returns true if it finds value in the tree, or false if it doesn’t find value in the tree. This function starts the recursive search by calling find_node() and passing in root.

Create a public function bool delete_node(int value). Use the following pseudo-code

bool delete_node(int value)
{
// use the following pseudo-code to delete a node
declare bool found, set to false
declare Node temp, set to root
declare Node parent, set to NULL

// find the node to delete and identify its parent
// this is iterative, rather than recursive
while not found and temp is NOT NULL
  if value equals temp->value
    set found to true
  else-if value < temp->value
    set parent to temp
    set temp to temp->left
 else-if value > temp->value 
    set parent to temp 
    set temp to temp->right 
  end-if
end-while

// there are 3 scenarios to handle
// 1 - the node to be deleted is a leaf
// you need to figure this part out

// 2 - the node to be deleted has one child
// you need to figure this part out

// 3 - a matching node has two children
// this case is given below
// when this node is deleted, something has to 
// take its place. This identifies that 
// node as the leaf node at the very left
// of the right subtree (wut?)
if found
  if temp->left is not NULL and temp->right is not NULL
    declare Node *replacement, set to temp->right
    while replacement->left is not NULL
      set parent to replacement
      set replacement to replacement->left
    end-while
    set temp->data to replacement->data
    set temp to replacement
  end-if

  Declare Node *subtree and set to temp->right
  if subtree is NULL
    set subtree to temp->left
  end-if

  if temp->data < parent->data
    set parent->left to subtree
  else
    set parent->right to subtree
  end-if
  
  delete temp
  return true
end-if
else
  return false;
}

In main(), ask the user to search for a value. Display a message indicating if the value was found or not. If it is found, ask the user if it should be deleted. If the user responds affirmatively, delete the matching node. Then, display the tree to confirm its deletion.

Sample main()

#include <iostream>
#include <string>

int main()
{
  BST bst;
  int values[25] = { 23, 117, 45, 19, 7, 13, 17, 40, 9, 11, 93, 49, 35, 8, 3, 10, 22, 77, 16, 6, 51, 57, 55, 90, 31 };

 
  return 0;
}

LEGEND
PROGRAM OUTPUT
USER INPUT
FROM INPUT

CATALOG ID: CPP-CHAL0059

Print Requirements

Tag: binary-search-tree

Challenge 59

Description

Requirements – PART 1

Requirements – Part 2

Sample main()