BST - Binary Search Tree (Iterative Function to Insert)

[ElPatoGarrido]

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

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):

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.

[Smac89]

What exactly doesn't work? Can you show example input/output?

[cire]

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:

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!]

[Smac89]

Only suggestion I can come up with is to not do this:

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

instead do:

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

[andywestken]

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.

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.

[ne555]

Simplifying cire's code

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

[ElPatoGarrido]

Thanks people, i used cire's code simplified by ne555 adding a break in case that you find a node with same value.

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