Question

1. Add the function int getNodeLevel (T value) to the Binary Search Tree class provided below. The function should return the level of the node value in the Binary Search Tree.

Hint:

Set currentNode to root

Initialize level = 0

while currentNode != Null

         if currentNode element = value return level

         else move to either the right child or the left child of the currentNode, update the loop, and repeat the loop

Function should return -1 if value is not in the tree

#include <iostream>
#include <vector>
using namespace std;

//****** The Node class for the Binary Search Tree ******
template<typename T>
class Node
{
public:
        Node();
        Node(T e, Node<T>* r, Node<T>* l);
        T element;          // holds the node element
        Node<T>* right;
        Node<T>* left;
};

//============ implementation of the constructors of the Node
template<typename T>
Node<T>::Node() { right = left = NULL; }

template<typename T>
Node<T>::Node(T e, Node<T>* r, Node<T>* l) { element = e; right = r; left = l; }

//===============  Binart Searct Tree (BST) class ===========

template<typename T>
class BTree
{
public:
        BTree() { root = NULL; }
        BTree(Node<T>* rt) { root = rt; }
        void BSTInsert(T value);
        void BSTRemove(T value);
        Node<T>* & getRoot() { return root; }  // returns the pointer to the root
        Node<T>*  BSTsearch(T value);

private:
        Node<T>* root;   // a pointer to the root of the tree
};

template<typename T>
Node<T>*  BTree<T>::BSTsearch(T value)
{
        // set cur to the tree root, traverse down the tree to find the element.
        // Do not use the root, if you move the root the tree will be lost.
        Node<T>* cur = root;
        while (cur != NULL)
        {
                if (value == cur->element)
                        return cur;
                else if (value < cur->element)
                        cur = cur->left;
                else
                        cur = cur->right;
        }
        return NULL;
}



// traverse down the tree and inserts at the bottom of the tree as a new leaf
template<typename T>
void BTree<T>::BSTInsert(T value)
{
        Node<T>* newNode = new Node<T>(value, NULL, NULL); // dynamically create a node with the given value
        if (root == NULL)    //Empty tree, fisrt node.
                root = newNode;
        else
        {
                Node<T>* r = root;
                while (r != NULL)
                {
                        if (value < r->element)
                        {
                                if (r->left == NULL)
                                {
                                        r->left = newNode; //insert the node 
                                        r = NULL;  // end the loop.
                                }
                                else
                                        r = r->left; // keep going to the left child
                        }
                        else
                        {
                                if (r->right == NULL)
                                {
                                        r->right = newNode;
                                        r = NULL;
                                }
                                else
                                        r = r->right;

                        }
                }
        }
}

//Three cases to consider when removing an element from a BST  
template<typename T>
void BTree<T>::BSTRemove(T value)
{
        Node<T>* parent = NULL;  // Need to track the parent of the node to be deleted
        Node<T>* current = root; // current will point to the node to be deleted
        //find the node to be removed
        while (current != NULL && current->element != value)
        {
                if (value < current->element)
                {
                        parent = current; current = current->left;
                }
                else
                {
                        parent = current; current = current->right;
                }
        }

        if (current != NULL) // The node to be deleted is found
        {
                //Case A : the node is a leaf node
                if (current->left == NULL && current->right == NULL)
                {
                        if (parent->right == current)
                                parent->right = NULL;
                        else
                                parent->left = NULL;
                        delete current;
                }

                //Case B: the node has two children
                // Must find the smalles element in the right subtree of the node, which is
                //found by going to the right child of the node then all the way to the left.
                else if (current->left != NULL && current->right != NULL)
                {
                        Node<T>* succ = current->right; // go to the right child of the node to be removed
                        parent = current;     // initialize parent node
                        if (succ->left == NULL)  // right child of the node has no left child
                        {
                                parent->right = succ->right;
                                current->element = succ->element;
                                delete succ;
                        }
                        else  //otherwise keep going left
                        {
                                while (succ->left != NULL)      // then find the smallest element in the left subtree
                                {
                                        parent = succ;
                                        succ = succ->left;
                                }
                                current->element = succ->element; //Replace the node to be deleted by the succ node
                                parent->left = NULL;  // skip the succ node
                                delete succ;
                        }
                }
                else  // Case C: Node has one child
                {
                if (root->element == value)    //if the node is the root node treat differently
                {
                        cout << "here\n";
                        if (root->right != NULL)
                                root = root->right;
                        else
                                root = root->left;
                }
                else    // a non root node with one child to be removed
                {
                        if (current->left != NULL)
                                parent->left = current->left;
                        else
                                parent->right = current->right;
                }
                delete current;
                }
        }
}

int main()
{
    BTree<int> bst;
    bst.BSTInsert(29);
    bst.BSTInsert(50);
    bst.BSTInsert(78);
    bst.BSTInsert(39);
    bst.BSTInsert(21);

    return 0;
}

Answer 1

//C++ program

#include<iostream>
using namespace std;

template<typename T>
class Node
{
public:
        Node();
        Node(T e, Node<T>* r, Node<T>* l);
        T element;          // holds the node element
        Node<T>* right;
        Node<T>* left;
};

//============ implementation of the constructors of the Node
template<typename T>
Node<T>::Node() { right = NULL;left = NULL; }

template<typename T>
Node<T>::Node(T e, Node<T>* r, Node<T>* l) { element = e; right = r; left = l; }

//=============== Binart Searct Tree (BST) class ===========

template<typename T>
class BTree
{
public:
        BTree() { root = NULL; }
        BTree(Node<T>* rt) { root = rt; }
        void BSTInsert(T value);
        void BSTRemove(T value);
        Node<T>* & getRoot() { return root; } // returns the pointer to the root
        Node<T>* BSTsearch(T value);
       int getNodeLevel (T value) ;
private:
        Node<T>* root;   // a pointer to the root of the tree
};

template<typename T>
Node<T>* BTree<T>::BSTsearch(T value)
{
        // set cur to the tree root, traverse down the tree to find the element.
        // Do not use the root, if you move the root the tree will be lost.
        Node<T>* cur = root;
        while (cur != NULL)
        {
                if (value == cur->element)
                        return cur;
                else if (value < cur->element)
                        cur = cur->left;
                else
                        cur = cur->right;
        }
        return NULL;
}

// traverse down the tree and inserts at the bottom of the tree as a new leaf
template<typename T>
void BTree<T>::BSTInsert(T value)
{
        Node<T>* newNode = new Node<T>(value, NULL, NULL); // dynamically create a node with the given value
        if (root == NULL)    //Empty tree, fisrt node.
                root = newNode;
        else
        {
                Node<T>* r = root;
                while (r != NULL)
                {
                        if (value < r->element)
                        {
                                if (r->left == NULL)
                                {
                                        r->left = newNode; //insert the node
                                        r = NULL; // end the loop.
                                }
                                else
                                        r = r->left; // keep going to the left child
                        }
                        else
                        {
                                if (r->right == NULL)
                                {
                                        r->right = newNode;
                                        r = NULL;
                                }
                                else
                                        r = r->right;

                        }
                }
        }
}

//Three cases to consider when removing an element from a BST
template<typename T>
void BTree<T>::BSTRemove(T value)
{
        Node<T>* parent = NULL; // Need to track the parent of the node to be deleted
        Node<T>* current = root; // current will point to the node to be deleted
        //find the node to be removed
        while (current != NULL && current->element != value)
        {
                if (value < current->element)
                {
                        parent = current; current = current->left;
                }
                else
                {
                        parent = current; current = current->right;
                }
        }

        if (current != NULL) // The node to be deleted is found
        {
                //Case A : the node is a leaf node
                if (current->left == NULL && current->right == NULL)
                {
                        if (parent->right == current)
                                parent->right = NULL;
                        else
                                parent->left = NULL;
                        delete current;
                }

                //Case B: the node has two children
                // Must find the smalles element in the right subtree of the node, which is
                //found by going to the right child of the node then all the way to the left.
                else if (current->left != NULL && current->right != NULL)
                {
                        Node<T>* succ = current->right; // go to the right child of the node to be removed
                        parent = current;     // initialize parent node
                        if (succ->left == NULL) // right child of the node has no left child
                        {
                                parent->right = succ->right;
                                current->element = succ->element;
                                delete succ;
                        }
                        else //otherwise keep going left
                        {
                                while (succ->left != NULL)      // then find the smallest element in the left subtree
                                {
                                        parent = succ;
                                        succ = succ->left;
                                }
                                current->element = succ->element; //Replace the node to be deleted by the succ node
                                parent->left = NULL; // skip the succ node
                                delete succ;
                        }
                }
                else // Case C: Node has one child
                {
                if (root->element == value)    //if the node is the root node treat differently
                {
                        cout << "here\n";
                        if (root->right != NULL)
                                root = root->right;
                        else
                                root = root->left;
                }
                else    // a non root node with one child to be removed
                {
                        if (current->left != NULL)
                                parent->left = current->left;
                        else
                                parent->right = current->right;
                }
                delete current;
                }
        }
}

template<typename T>
int BTree<T>::getNodeLevel (T value) {
   Node<T> *currentNode = root;
   int level = 0;
   while (currentNode != NULL){
       if(currentNode->element == value) return level;
       else if(currentNode->element < value)
           currentNode = currentNode->right;
       else
           currentNode = currentNode->left;
       level = level + 1;
   }
   return -1;
}

int main()
{
    BTree<int> bst;
    bst.BSTInsert(29);
    bst.BSTInsert(50);
    bst.BSTInsert(78);
    bst.BSTInsert(39);
    bst.BSTInsert(21);

    return 0;
}