Reputation: 231
Iterative BST insertion in C++
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.
Upvotes: 7
Views: 15699
Answers (8)
Reputation: 1
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;
}
}
Upvotes: 0
Reputation: 1396
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
Upvotes: 0
Reputation: 11
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;
}
}
Upvotes: 0
Reputation: 231
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.
Upvotes: 6
Reputation: 490098
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.
Upvotes: 6
Reputation: 955
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;
Upvotes: 1
Reputation: 971
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.
Upvotes: 0
Reputation: 1513
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;
}
Upvotes: 0
Related Questions
- Recursive insertion of BST
- Insert a node in BST with global root
- Correctly inserting nodes into a BST in C++
- What's wrong with this code for BST insertion?
- binary tree insert function
- bst insert recursion c++
- BinaryTree Insertion
- C++ iterative insert into binary search tree BST
- Insertion iterative approach to BST (C)
- help with insert on first BST