Question

In C++

Consider the binary search tree implementation in file bintree.cp
a)Add to the TreeNode class a pointer to the parent node. Modify the insert and erase functions to properly set those pointers.

b)Then define a TreeIterator class that contains a pointer to a TreeNode and has member functions get and next.

i)The iterator’s get member function should return the data value of the node to which it points.
ii)The iterator’s next member function should find the next element in in-order traversal.
*If the current node has a right child, then the next node is the leftmost leave of the right child.

*If the current node does not have a right child, keep moving up to the parent until the previously traversed node is a left child. The next node is the parent of this left child.

c)Add a begin member function to the BinarySearchTree class. It should return an iterator that points to the leftmost leaf of the tree.

//bintree.cp

#include <iostream>
#include <string>

using namespace std;

class TreeNode
{
public:
void insert_node(TreeNode* new_node);
void print_nodes() const;
bool find(string value) const;
private:
string data;
TreeNode* left;
TreeNode* right;
friend class BinarySearchTree;
};

class BinarySearchTree
{
public:
BinarySearchTree();
void insert(string data);
void erase(string data);
int count(string data) const;
void print() const;
private:
TreeNode* root;
};

BinarySearchTree::BinarySearchTree()
{
root = NULL;
}

void BinarySearchTree::print() const
{
if (root != NULL)
root->print_nodes();
}

void BinarySearchTree::insert(string data)
{
TreeNode* new_node = new TreeNode;
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
if (root == NULL) root = new_node;
else root->insert_node(new_node);
}

void TreeNode::insert_node(TreeNode* new_node)
{
if (new_node->data < data)
{
if (left == NULL) left = new_node;
else left->insert_node(new_node);
}
else if (data < new_node->data)
{
if (right == NULL) right = new_node;
else right->insert_node(new_node);
}
}

int BinarySearchTree::count(string data) const
{
if (root == NULL) return 0;
else if (root->find(data)) return 1;
else return 0;
}

void BinarySearchTree::erase(string data)
{
// Find node to be removed

TreeNode* to_be_removed = root;
TreeNode* parent = NULL;
bool found = false;
while (!found && to_be_removed != NULL)
{
if (to_be_removed->data < data)
{
parent = to_be_removed;
to_be_removed = to_be_removed->right;
}
else if (data < to_be_removed->data)
{
parent = to_be_removed;
to_be_removed = to_be_removed->left;
}
else found = true;
}

if (!found) return;

// to_be_removed contains data

// If one of the children is empty, use the other

if (to_be_removed->left == NULL || to_be_removed->right == NULL)
{
TreeNode* new_child;
if (to_be_removed->left == NULL)
new_child = to_be_removed->right;
else
new_child = to_be_removed->left;
if (parent == NULL) // Found in root
root = new_child;
else if (parent->left == to_be_removed)
parent->left = new_child;
else
parent->right = new_child;
return;
}
  
// Neither subtree is empty

// Find smallest element of the right subtree

TreeNode* smallest_parent = to_be_removed;
TreeNode* smallest = to_be_removed->right;
while (smallest->left != NULL)
{
smallest_parent = smallest;
smallest = smallest->left;
}

// smallest contains smallest child in right subtree

// Move contents, unlink child
to_be_removed->data = smallest->data;
if (smallest_parent == to_be_removed)
smallest_parent->right = smallest->right;
else
smallest_parent->left = smallest->right;
}

bool TreeNode::find(string value) const
{
if (value < data)
{
if (left == NULL) return false;
else return left->find(value);
}
else if (data < value)
{
if (right == NULL) return false;
else return right->find(value);
}
else
return true;
}

void TreeNode::print_nodes() const
{
if (left != NULL)
left->print_nodes();
cout << data << "\n";
if (right != NULL)
right->print_nodes();
}

int main()
{
BinarySearchTree t;
t.insert("D");
t.insert("B");
t.insert("A");
t.insert("C");
t.insert("F");
t.insert("E");
t.insert("I");
t.insert("G");
t.insert("H");
t.insert("J");
t.erase("A"); // Removing leaf
t.erase("B"); // Removing element with one child
t.erase("F"); // Removing element with two children
t.erase("D"); // Removing root
t.print();
cout << t.count("E") << "\n";
cout << t.count("F") << "\n";
return 0;
}

Answer 1

Below is completed code. Let me know if you have any problem or doubt. Thank you.

====================================================================

#include <iostream>
#include <string>

using namespace std;

class TreeNode
{
public:
    void insert_node(TreeNode* new_node);
    void print_nodes() const;
    bool find(string value) const;
private:
    string data;
    TreeNode* left;
    TreeNode* right;
    TreeNode* parent;
    friend class BinarySearchTree;
    friend class TreeIterator;
};

class TreeIterator
{
public:
    TreeIterator(TreeNode* root);
    string get();
    TreeNode* next();
private:
    TreeNode* current;
};

class BinarySearchTree
{
public:
    BinarySearchTree();
    void insert(string data);
    void erase(string data);
    int count(string data) const;
    void print() const;
    TreeIterator& begin();
private:
    TreeNode* root;
};

BinarySearchTree::BinarySearchTree()
{
    root = NULL;
}

void BinarySearchTree::print() const
{
    if (root != NULL)
        root->print_nodes();
}

void BinarySearchTree::insert(string data)
{
    TreeNode* new_node = new TreeNode;
    new_node->data = data;
    new_node->left = NULL;
    new_node->right = NULL;
    new_node->parent = NULL;
    if (root == NULL) root = new_node;
    else root->insert_node(new_node);
}

void TreeNode::insert_node(TreeNode* new_node)
{
    if (new_node->data < data)
    {
        if (left == NULL)
        {
            left = new_node;
            new_node->parent = this;
        }
        else left->insert_node(new_node);
    }
    else if (data < new_node->data)
    {
        if (right == NULL)
        {
            right = new_node;
            new_node->parent = this;
        }
        else right->insert_node(new_node);
    }
}

int BinarySearchTree::count(string data) const
{
    if (root == NULL) return 0;
    else if (root->find(data)) return 1;
    else return 0;
}

void BinarySearchTree::erase(string data)
{
    // Find node to be removed

    TreeNode* to_be_removed = root;
    bool found = false;
    while (!found && to_be_removed != NULL)
    {
        if (to_be_removed->data < data)
        {
            to_be_removed = to_be_removed->right;
        }
        else if (data < to_be_removed->data)
        {
            to_be_removed = to_be_removed->left;
        }
        else found = true;
    }

    if (!found) return;

    // to_be_removed contains data
  
    // If one of the children is empty, use the other

    if (to_be_removed->left == NULL || to_be_removed->right == NULL)
    {
        TreeNode* new_child;
        if (to_be_removed->left == NULL)
            new_child = to_be_removed->right;
        else
            new_child = to_be_removed->left;
        if (to_be_removed->parent == NULL) // Found in root
            root = new_child;
        else if (to_be_removed->parent->left == to_be_removed)
            to_be_removed->parent->left = new_child;
        else
            to_be_removed->parent->right = new_child;
        // assign parent
        if(new_child != NULL) // to_be_removed can be leaf node
            new_child->parent = to_be_removed->parent;
        // free memory
        delete to_be_removed;
        return;
    }

    // Neither subtree is empty

    // Find smallest element of the right subtree

    TreeNode* smallest = to_be_removed->right;
    while (smallest->left != NULL)
        smallest = smallest->left;
  
    // smallest contains smallest child in right subtree

    // Move contents, unlink child
    to_be_removed->data = smallest->data;
    if (smallest->parent == to_be_removed)
        smallest->parent->right = smallest->right;
    else
        smallest->parent->left = smallest->right;

    // set parent link
    if (smallest->right != NULL) // smallest can be leaf node
        smallest->right->parent = smallest->parent;
    // free memory
    delete smallest;
}

bool TreeNode::find(string value) const
{
    if (value < data)
    {
        if (left == NULL) return false;
        else return left->find(value);
    }
    else if (data < value)
    {
        if (right == NULL) return false;
        else return right->find(value);
    }
    else
        return true;
}

void TreeNode::print_nodes() const
{
    if (left != NULL)
        left->print_nodes();
    cout << data << "\n";
    if (right != NULL)
        right->print_nodes();
}

TreeIterator& BinarySearchTree::begin()
{
    // create new iterator from root
    TreeIterator* iter = new TreeIterator(root);
    return *iter;
}

TreeIterator::TreeIterator(TreeNode* root)
{
    // initailize current node
    current = root;
    // set left most node as current node
    if (current != NULL)
    {
        while (current->left != NULL)
            current = current->left;
    }
}

string TreeIterator::get() {
    if (current != NULL)
    {
        return current->data;
    }
    return "";
}

TreeNode* TreeIterator::next() {
    if (current == NULL)
        return NULL;
    // If the current node has a right child,
    // then the next node is the leftmost leave of the right child
    if (current->right != NULL)
    {
        current = current->right;
        while (current->left != NULL)
            current = current->left;
    }
    else
    {
        // If the current node does not have a right child,
        // keep moving up to the parent until the previously
        // traversed node is a left child
        while (current->parent != NULL && current->parent->left != current)
            current = current->parent;
        // The next node is the parent of this left child
        current = current->parent;
    }
    return current;
}

int main()
{
    BinarySearchTree t;
    t.insert("D");
    t.insert("B");
    t.insert("A");
    t.insert("C");
    t.insert("F");
    t.insert("E");
    t.insert("I");
    t.insert("G");
    t.insert("H");
    t.insert("J");

    cout << "Print tree from iterator:" << endl;
    TreeIterator iter = t.begin();
    do
    {
        cout << iter.get() << " ";
    } while (iter.next() != NULL);
    cout << endl;

    t.erase("A"); // Removing leaf
    t.erase("B"); // Removing element with one child
    t.erase("F"); // Removing element with two children
    t.erase("D"); // Removing root
    t.print();
    cout << t.count("E") << "\n";
    cout << t.count("F") << "\n";
  
    cout << "Print tree from iterator after delete:" << endl;
    iter = t.begin();
    do
    {
        cout << iter.get() << " ";
    } while (iter.next() != NULL);
    cout << endl;

    return 0;
}

====================================================================