### BST - Binary Search Tree (Iterative Function to Insert)

Hi, i was studying BST and tried to make a iterative function to insert, the original recursive function is the following:

 ``1234567891011`` ``````void insert(node *&tree, int value) { if (!tree) { tree = new node; tree->num = value; tree->left = tree->right = NULL; } else if (value < tree->num) insert(tree->left, value); else if (value > tree->num) insertar(tree->right, value); }``````

And the code that i did is (but doesn't work):

 ``1234567891011121314151617181920`` ``````void insert(node *&tree, int value) { if (!tree) { tree = new node; tree->num = value; tree->left = tree->right = NULL; } else { node *aux = tree; while (aux) if (value < aux->num) aux = aux->left; else if (value > aux->num) aux = aux->right; aux = new node; aux->dato = value; aux->left = aux->right = NULL; } }``````

So i ask if someone can help me with this, i don't see where the error is or why it doesn't work.
Last edited on
What exactly doesn't work? Can you show example input/output?
aux stops existing when your function ends, so any changes made to it are lost when the function ends. I assume that's a typo on line 17.

Untested:
 ``12345678910111213141516171819202122232425262728293031323334353637383940`` ``````void insert(node *&tree, int value) { if (!tree) { tree = new node; tree->num = value; tree->left = tree->right = NULL; } else { node * cur = tree ; for ( ; ; ) { while ( value < cur->num ) { if ( cur->left ) cur = cur->left ; else { cur->left = new node ; cur->left->num = value ; cur->left->left = cur->left->right = nullptr ; return ; } } while ( value > cur->num ) { if ( cur->right ) cur = cur->right ; else { cur->right = new node ; cur->right->num = value ; cur->right->left = cur->right->right = nullptr ; return ; } } } } }``````

[edit: If the value inserted is already in the tree, this will cause an infinite loop. Might want to fix that!]
Last edited on
Only suggestion I can come up with is to not do this:

`tree->left = tree->right = NULL;`

 ``12`` ``````tree->left = NULL; tree->right = NULL;``````
Given it's C++, there should be no need for the line:

`tree->left = tree->right = NULL;`

as the node struct/class should be looking after itself, e.g.

 ``12345678`` ``````struct node { node() : left(NULL), right(NULL), num(0) { } node *left; node *right; int num; // or dato };``````

or even handle the data via a construtor, etc.
Simplifying cire's code
 ``12345678910111213`` ``````node *aux = tree, *parent; while (aux){ parent = aux; if (value < aux->num) aux = aux->left; else if (value > aux->num) aux = aux->right; } if( parent->num < value ) parent->right = new node(value); else parent->left = new node(value);``````
there is still the infinite loop if the value is already in, ;P
Thanks people, i used cire's code simplified by ne555 adding a break in case that you find a node with same value.

 ``1234567891011121314151617181920212223`` ``````void insert(node *&tree, int value) { if (!tree) tree = new node(value); else { node *aux = tree; node *aux_2 = aux; while (aux) { aux_2 = aux; if (value < aux->num) aux = aux->izq; else if (value > aux->num) aux = aux->der; else if (value == aux->num) break; } if (value < aux_2->num) aux_2->left = new node(value); else if (value > aux_2->num) aux_2->right = new node(value); } }``````
Topic archived. No new replies allowed.