Iterative BST insertion in C++

Question

I am trying to understand BSTs and how to insert elements into it iteratively. My node structure implementation looks like so:

struct Node{
    Node *left;
    Node *right;
    T data; //template class   
};

And my insertion implementation looks like so:

template<typename T>
bool BST<T>::Insert(const T value)
{
   Node *newNode = new Node;

   newNode -> data = value;
   newNode -> left = NULL; 
   newNode -> right = NULL;

   if(root == NULL) {root = newNode;} //If the BST is empty
   else 
   {//The BST is not empty 
      Node *ptr = root; //points to the current Node
      Node *ptr_parent; //points to the parent Node

      while(ptr != NULL)
      {
         if((ptr -> data) > value)
         {   
            ptr_parent = ptr;    
            ptr = ptr -> left;
         }

         if((ptr -> data) < value)
         {
            ptr_parent = ptr;
            ptr = ptr -> right;
         }
      }
    }

      ptr = newNode; //insert the newNode at the spot
      if((ptr_parent -> data) < value)
         ptr_parent -> right = newNode;
      else
         ptr_parent -> left = newNode; 

   return true;
}

The insertion works when adding the first Node into an empty tree but I get a segmentation fault whenever i try to add more Nodes. I understand that there are posts that show how to implement insertions into BSTs but most of them show the recursive method, and those with iterative examples are incomplete or too specific. Thank you.

Edmondo

What does your debugger show you? – Puryear

From looking at it, I almost certain that something is wrong with the way I traverse the tree to find the insertion point... – Edmondo

@ StarPilot: it only says Seg fault. Core dump I use Vim to compile my code – Edmondo

Looking at the code, I see that on the first insert, you set root to newNode. Then you let the code fall through. So, ptr = newNode; ptr_parent -> left = newNode; return true; on the first pass. So your root node now has a left = itself. This is not the layout you want. As traversing root -> left will always go back to itself and result in a loop until the program blows. When you set root, have it just return true; from there and see what happens. – Puryear

Answer 1

I was able to make my original code work last night, I'm sharing the answer here:

template<typename T>
bool BST<T>::Insert(const T value)
{
   Node *ptr;
   Node *ptr_parent;

   if(root == NULL)
   {//The BST is Empty...
      Node *newNode = new Node;
      newNode -> data = value;
      newNode -> left = NULL;
      newNode -> right = NULL;

      root = newNode;
      ptr = root;
   } else { //traversing the tree to find the insertion point
      ptr = root;
      while(ptr != NULL)
      {
         if((ptr -> data) == value) {return false;} //to check for duplicates

         if(value < (ptr -> data))
         {
            ptr_parent = ptr;
            ptr = ptr -> left;
         } else {
            ptr_parent = ptr;
            ptr = ptr -> right;
         }
      }
      Node *newNode = new Node;

      newNode -> data = value;
      newNode -> left = NULL;
      newNode -> right = NULL;

      //checking for parent value to determine if
      //the Node is a left or right child  
      if(value < (ptr_parent -> data))
         ptr_parent -> left = newNode;
      else
         ptr_parent -> right = newNode;
   }

   ++count;//to keep track of the Node count
   return true;      
}

For my own sake I wanted to solve this without using double pointers.

Edmondo

Was root declared global or local? – Franck

@AnujGarg of course it's global. The code would throw compilation error otherwise. – Subsidize

Answer 2

I think I'd do things a little differently. First, I'd simplify the other code a little by adding a ctor to the Node class:

struct Node{
    Node *left;
    Node *right;
    T data; 

    Node(T const &data) : left(nullptr), right(nullptr), data(data) {}
};

Then you can use a pointer to a pointer to traverse the tree and insert the item:

bool insert(const T value) {
    Node **pos;
    for (pos = &root; *pos != nullptr;) {
        if (value < (*pos)->value) 
            pos = &(*pos)->left;
        else if ((*pos)->value < value ) 
            pos = &(*pos)->right;
        else 
            return false;
    }
    *pos = new Node(value);
    return true;
}

Note that I've delayed creating the new node until after we've dropped out of the loop. This way, if we have a duplicate element, we can just return (without leaking a node, since we haven't allocated a new node yet).

For what it's worth, if you were going to do this recursively, it would probably be easier to use a reference to a pointer instead of a pointer to a pointer.

Thumbscrew

Answer 3

You didn't handle the case when ptr->data == value so the loop will be infinite whenever a duplicate is found, and ptr = newNode doesn't do anything, it just makes ptr point to newNode. Try this

//ptr holds the address of pointers to nodes.
Node **ptr = &root;

while(*ptr != NULL){

  if((*ptr)->data > T)
    ptr = &(*ptr)->right;
  else
    ptr = &(*ptr)->left;
  //Not handling duplicates
}
//Change the value of the pointer to newNode
*ptr = newNode;

Thereunder

Is there a way to avoid double pointers when you insert in a BST? the above post suggests double pointers as well, so im trying to see what changes are needed to make my code compile. – Edmondo

PS: thanks for pointing about the duplicate case. I forgot about that – Edmondo

You can avoid double pointer by using 2 pointers as you originally did. – Thereunder

Answer 4

Use hard pointers

Node **ptr = &root; //points to the current Node
Node **ptr_parent; //points to the parent Node

When you are trying to do this

ptr = newNode; //insert the newNode at the spot

it doesn't do anyithing because you need to modify the pointer which points to the left or the right subnode

something like this:

template<typename T>
bool BST<T>::Insert(const T value)
{
    Node *newNode = new Node;

    newNode -> data = value;
    newNode -> left = NULL; 
    newNode -> right = NULL;

    if(root == NULL) {root = newNode;} //If the BST is empty
    else 
    {//The BST is not empty 
        Node **ptr = &root; //points to the current Node
        Node **ptr_parent; //points to the parent Node

        while((*ptr) != NULL)
        {
            if(((*ptr) -> data) > value)
            {   
                ptr_parent = ptr;    
                    ptr = &ptr -> left;
            }   

            if(((*ptr) -> data) < value)
            {
                    ptr_parent = ptr;
                    ptr = &ptr -> right;
            }
            }
        }

    (*ptr) = newNode; //insert the newNode at the spot
    if(((*ptr_parent) -> data) < value)
        (*ptr_parent) -> right = newNode;
        else
                (*ptr_parent) -> left = newNode; 

    return true;
}       

Woad

I was trying to figure out how the implementation would work with double pointers. But just by copy/pasting this implementation I get a few compilation errors I need to debug. I'll get back to you once I figure out what changes are needed. – Edmondo

bst.h:103:21: error: request for member ‘left’ in ‘* ptr’, which is of non-class type ‘BST<int>::Node*’ bst.h:109:21: error: request for member ‘right’ in ‘* ptr’, which is of non-class type ‘BST<int>::Node*’ – Edmondo

Answer 5

As I understand, it is failing because of following line:

ptr = newNode; //insert the newNode at the spot

after the while loop your ptr is NULL otherwise you can not exit from the while loop. You are assigning a struct to NULL, which is not right.

Hopefully this helps. Everything else looks normal.

Paluas

That makes sense. I guess I was thinking about this too much as a "linked list" rather than its own ADT... – Edmondo

Won't it just make ptr to point to newNode? How is it the error? – Thereunder

Answer 6

void insert(node* root, int value)
{
    if (root == NULL)
    {
        root = new node;
        root->data = value;
        return;
    }
    while(!((root->data < value && root->right == NULL) || (root->data >= value && root->left == NULL)))
    {
        if (root->data < value)
            root = root->right;
        else
            root = root->left;
    }
    if (root->data < value)
    {
        root->right = new node;
        root->right->data = value;
    } else 
    {
        root->left = new node;
        root->left->data = value;
    }
}

Stodder

Answer 7

template <class T>
class TreeNode{
private:
    T data;
    TreeNode<T>* right,*left;
public:
void setData(T d){
    this->data =d;
}
T getData(){
    return this->data;
}
void setRight(TreeNode<T>* r){
    this->right =r;
}
TreeNode<T>* getRight(){
    return this->right;
}
void setLeft(TreeNode<T>* r){
    this->left =r;
}
TreeNode<T>* getLeft(){
    return this->left;
}
static TreeNode<T>* newNode(T data){
    TreeNode<T>* n = new TreeNode<T>();
    n->setData(data);
    n->setRight(NULL);
    n->setLeft(NULL);
    return n;
}
};



template <class T>
class BinaryTree{
private:
        TreeNode<T>* root;
public:
    void insert(T data){
        TreeNode<T>* n = TreeNode<T>::newNode(data);

        if(root==NULL)
            root = n;
        else{
        TreeNode<T>* t = root;
        while(t!=NULL){

            if(n->getData() >= t->getData()){
                if(t->getRight()==NULL){
                    t->setRight(n); //newnode attached as right child in tree
                    t = NULL;
                }
                else
                    t = t->getRight();
            }
            else{
                if(t->getLeft()==NULL){
                    t->setLeft(n); //newnode attached as left child in tree
                    t=NULL;
                }
                else
                    t = t->getLeft();
            }
        }

        }

    }

    void preorder(){
        TreeNode<T>* t = root;
        preorderUtil(t);
    }

    void preorderUtil(TreeNode<T>* node){
        if(node==NULL)
            return;
        preorderUtil(node->getLeft());
        cout<<node->getData()<<" ";
        preorderUtil(node->getRight());
    }
};

I answered a case here Binary Search Tree insertion doesn't work see if it helps

Dixon

Answer 8

void insert(int val)
    {
        Node *newNode;
        newNode=new Node;
        newNode->data=val;
        Node *currentNode=root;
        Node *parentNode;
        
        if(root==NULL)
        {
            newNode->left=NULL;
            newNode->right=NULL;
        }
        
            
        else
        {
            
            
            while(currentNode!=NULL)
            {
                if((currentNode->data)>val)
                {
                    parentNode=currentNode;
                    currentNode=currentNode->left;
                }
                
                if((currentNode->data)<val)
                {
                    parentNode=currentNode;
                    currentNode=currentNode->right;
                }
            }
        
        }
        currentNode=newNode;
        if((parentNode->data)<val)
        {
            parentNode->right=newNode;
        }
        else
        {
        parentNode->right=newNode;
        }
        
    }

Emrick

Welcome to Stack Overflow! While this code snippet may solve the question, including an explanation really helps to improve the quality of your post. Remember that you are answering the question for readers in the future, and those people might not know the reasons for your code suggestion. Please also try not to crowd your code with explanatory comments, this reduces the readability of both the code and the explanations! – Staffan