lundi 25 mai 2020

Recursion in Binary Search Tree construction

Below is the code implementation of binary search tree construction in C++. My confusion is I am not able to trace the recursion stack. Consider the below tree. Now I want to remove the node 10. SO this will jump to the line in the code that checks if both left and right subtree are not null and it will try to find the least value in the right subtree and that is 11 in this case. and it will recursively call remove function again . Now I have one doubt - when remove is recursively called again - first it removes 11 from that position in the original tree and return 11 from the function that is received by first remove function on the stack, but then which line in the code actually updates 11 to the root. I am really not getting this in my head. Please help me out.

10 / \ 6 12 \ / \ 8 11 15

#include <bits/stdc++.h>
using namespace std;


class BST
{
    public:
      int value;
      BST *left;
      BST *right;

      BST(int val)
      {
          value = val;
          left = NULL;
          right = NULL;
      }


      BST &insert(int val)
      {
          BST *currentNode = this;  //this points to the current object of BST class. For instance if you created
          //root node with value 10. this will store the reference to the root node object
          while(true)
          {
              if (val < currentNode->value)  //go to left subtree
              {
                  if (currentNode->left == NULL)  //if null insert
                  {
                      BST *newNode = new BST(val);
                      currentNode->left = newNode;  //update the address 
                      break;
                  }
                  else 
                  {
                      currentNode = currentNode->left;  //if not null then keep traversing
                  }
              }
              else 
              {
                  if (currentNode->right == NULL)
                  {
                      BST *newNode = new BST(val);
                      currentNode->right = newNode;
                      break;
                  }
                  else 
                  {
                      currentNode = currentNode->right;
                  }
              }
          }

          return *this;  
      }


      bool contains(int val)
      {
          BST *currentNode = this;
          while(currentNode != NULL)
          {
              if (val < currentNode->value)
                  currentNode = currentNode->left;  //if value is less then keep traversing left
              else if (val > currentNode->value)
                  currentNode = currentNode->right; //if value is greater then keep traversing right
              else 
                 return true;
          }

          return false;
      }


      BST &remove(int val, BST *parentNode = NULL)
      {
          BST *currentNode = this;
          while (currentNode != NULL)
          {
              if (val < currentNode->value)
              {
                  parentNode = currentNode;
                  currentNode = currentNode->left;
              }
              else if (val > currentNode->value)
              {
                  parentNode = currentNode;
                  currentNode = currentNode->right;
              }
              //Up until above line the code first searches for the element to be removed
              else 
              {
                  if (currentNode->left != NULL && currentNode->right != NULL)  //this node checks if it has
                  //left and right child both and if yes then find the least value in the right subtree and then
                  //remove that node from that position
                  {
                      currentNode->value = currentNode->right->getMinValue();
                      currentNode->right->remove(currentNode->value,currentNode);
                  }

                  else if (parentNode == NULL) //this is special case of root node where there may be only
                  //left child existing or only right child. If both exist then above logic takes care of that
                  {
                      if (currentNode->left != NULL)
                      {
                          currentNode->value = currentNode->left->value;
                          currentNode->right = currentNode->left->right;
                          currentNode->left = currentNode->left->left;
                      }
                      else if (currentNode->right != NULL)
                      {
                          currentNode->value = currentNode->right->value;
                          currentNode->left = currentNode->right->left;
                          currentNode->right = currentNode->right->right;
                      }
                      else 
                      {} //This is for single node tree. Do nothing
                  }

                  else if (parentNode->left == currentNode)  //this condition if the parent node left child is 
                  //the node to be removed . Then we can do simple one liner and update the node 
                  {
                      parentNode->left = currentNode->left != NULL ? currentNode->left : currentNode->right;
                  }
                  else if (parentNode->right == currentNode)
                  {
                      parentNode->right = currentNode->left != NULL ? currentNode->left : currentNode->right;
                  }

                  break;
              }
          }

          return *this;
      }

      int getMinValue()
      {
          if (left == NULL)
              return value;
          else 
             return left->getMinValue();
      }

      void show()
      {
          BST *currentNode = this;
          cout<<currentNode->value;

      }
};




int main()
{

    int value = 10;
    BST b1(value);
    b1.insert(12);
    b1.insert(6);
    b1.insert(8);
    b1.insert(15);
    b1.insert(11);
    b1.remove(10);
    b1.show();


}

Aucun commentaire:

Enregistrer un commentaire