Iterative insertion of BST in C ++

Question

I am trying to understand BST and how to insert elements into iteratively. My implementation of the node structure looks like this:

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

And my insert implementation looks 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; } 

The insert works when adding the first node to an empty tree, but I get a segmentation error whenever I try to add additional nodes. I understand that there are posts that show how to embed inserts in BST, but most of them show a recursive method, and those that have iterative examples are incomplete or too specific. Thanks.

Answer 1

I was able to do my work with the source code last night, I share 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 myself, I wanted to solve this without using double pointers.

Answer 2

I think I would have done differently. First, I would simplify the other code a bit by adding 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 the pointer to the pointer to move through the tree and insert the element:

 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 delayed the creation of the new Node until we exit the loop. That way, if we have a repeating element, we can just go back (no leak node, since we haven't allocated a new Node yet).

What is it worth, if you are going to do it recursively, it would probably be easier to use a link to a pointer instead of a pointer to a pointer.

Answer 3

You did not handle the case where ptr->data == value , so the loop will be infinite whenever a duplicate is found, and ptr = newNode does nothing, it just points ptr to newNode . try it

 //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; 

Answer 4

Use hard pointers

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

When you try to do it

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

it does nothing because you need to change the pointer pointing to the left or right trays

something like that:

 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; } 

Answer 5

As I understand it, it does not work due to the following line:

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

after the while loop, your ptr is NULL, otherwise you cannot exit the while loop. You assign a NULL structure, which is incorrect.

Hope this helps. Everything else looks fine.

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; } } 

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 this case here Inserting a binary search does not work if it helps