Insertar un Node en el árbol de búsqueda binaria iterativamente

Un enfoque recursivo para insertar un nuevo Node en un BST ya se analiza en la publicación: Árbol de búsqueda binaria | CONJUNTO 1 . En esta publicación, se analiza un enfoque iterativo para insertar un Node en BST.
 

Inserción de una llave

Siempre se inserta una nueva clave en el Node hoja. Comience a buscar una clave desde la raíz hasta que lleguemos a un Node de hoja. Una vez que se encuentra un Node hoja, el nuevo Node se agrega como elemento secundario del Node hoja.
Ejemplo : 
 

Entrada: Para el inserto BST dado 40 
 

Producción: 
 

Explicación: El nuevo Node 40 es un Node hoja. Comience a buscar desde la raíz hasta que se alcance un Node hoja, es decir, mientras busca si un nuevo valor es mayor que el Node actual, muévase al elemento secundario derecho, de lo contrario, al elemento secundario izquierdo. 
Entrada: Al BST dado inserte 600 
 

Producción: 
 

Explicación: El nuevo Node 600 es un Node hoja. Comience a buscar desde la raíz hasta que se alcance un Node hoja, es decir, mientras busca si un nuevo valor es mayor que el Node actual, muévase al elemento secundario derecho, de lo contrario, al elemento secundario izquierdo. 
 

Solución: 
Enfoque : 
 

• Cabe señalar que las claves nuevas siempre se insertan en el Node hoja.
• Comience desde la raíz y ejecute un ciclo hasta que se alcance un puntero nulo.
• Mantenga almacenado el puntero anterior del Node actual.
• Si el Node actual es nulo, cree e inserte el nuevo Node allí y conviértalo en uno de los elementos secundarios del Node principal/anterior según su valor.
• Si el valor del Node actual es menor que el nuevo valor, muévase al elemento secundario derecho del Node actual; de lo contrario, muévase al elemento secundario izquierdo.

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ program to demonstrate insert operation
// in binary search tree
#include <bits/stdc++.h>
using namespace std;
 
// BST node
struct Node {
    int key;
    struct Node *left, *right;
};
 
// Utility function to create a new node
Node* newNode(int data)
{
    Node* temp = new Node;
 
    temp->key = data;
 
    temp->left = NULL;
    temp->right = NULL;
 
    return temp;
}
 
// A utility function to insert a new
// Node with given key in BST
Node* insert(Node* root, int key)
{
    // Create a new Node containing
    // the new element
    Node* newnode = newNode(key);
 
    // Pointer to start traversing from root and
    // traverses downward path to search
    // where the new node to be inserted
    Node* x = root;
 
    // Pointer y maintains the trailing
    // pointer of x
    Node* y = NULL;
 
    while (x != NULL) {
        y = x;
        if (key < x->key)
            x = x->left;
        else
            x = x->right;
    }
 
    // If the root is NULL i.e the tree is empty
    // The new node is the root node
    if (y == NULL)
        y = newnode;
 
    // If the new key is less than the leaf node key
    // Assign the new node to be its left child
    else if (key < y->key)
        y->left = newnode;
 
    // else assign the new node its right child
    else
        y->right = newnode;
 
    // Returns the pointer where the
    // new node is inserted
    return y;
}
 
// A utility function to do inorder
// traversal of BST
void Inorder(Node* root)
{
    if (root == NULL)
        return;
    else {
        Inorder(root->left);
        cout << root->key << " ";
        Inorder(root->right);
    }
}
 
// Driver code
int main()
{
    /* Let us create following BST
            50
          /   \
        30      70
        / \   / \
       20 40 60 80 */
 
    Node* root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);
 
    // Print inorder traversal of the BST
    Inorder(root);
 
    return 0;
}

// Java program to demonstrate insert operation
// in binary search tree
import java.util.*;
class solution
{
   
// BST node
static class Node {
    int key;
     Node left, right;
};
   
// Utility function to create a new node
static Node newNode(int data)
{
    Node temp = new Node();
   
    temp.key = data;
   
    temp.left = null;
    temp.right = null;
   
    return temp;
}
   
// A utility function to insert a new
// Node with given key in BST
static Node insert(Node root, int key)
{
    // Create a new Node containing
    // the new element
    Node newnode = newNode(key);
   
    // Pointer to start traversing from root and
    // traverses downward path to search
    // where the new node to be inserted
    Node x = root;
   
    // Pointer y maintains the trailing
    // pointer of x
    Node y = null;
   
    while (x != null) {
        y = x;
        if (key < x.key)
            x = x.left;
        else
            x = x.right;
    }
   
    // If the root is null i.e the tree is empty
    // The new node is the root node
    if (y == null)
        y = newnode;
   
    // If the new key is less than the leaf node key
    // Assign the new node to be its left child
    else if (key < y.key)
        y.left = newnode;
   
    // else assign the new node its right child
    else
        y.right = newnode;
   
    // Returns the pointer where the
    // new node is inserted
    return y;
}
   
// A utility function to do inorder
// traversal of BST
static void Inorder(Node root)
{
    if (root == null)
        return;
    else {
        Inorder(root.left);
        System.out.print( root.key +" ");
        Inorder(root.right);
    }
}
   
// Driver code
public static void main(String args[])
{
    /* Let us create following BST 
            50 
          /   \ 
        30      70 
        / \   / \ 
       20 40 60 80 */
   
    Node root = null;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);
   
    // Print inorder traversal of the BST
    Inorder(root);
   
}
}
//contributed by Arnab Kundu

"""Python3 program to demonstrate insert
operation in binary search tree """
 
# A Binary Tree Node
# Utility function to create a
# new tree node
class newNode:
 
    # Constructor to create a newNode
    def __init__(self, data):
        self.key= data
        self.left = None
        self.right = self.parent = None
 
# A utility function to insert a new
# Node with given key in BST
def insert(root, key):
 
    # Create a new Node containing
    # the new element
    newnode = newNode(key)
 
    # Pointer to start traversing from root
    # and traverses downward path to search
    # where the new node to be inserted
    x = root
 
    # Pointer y maintains the trailing
    # pointer of x
    y = None
 
    while (x != None):
        y = x
        if (key < x.key):
            x = x.left
        else:
            x = x.right
     
    # If the root is None i.e the tree is
    # empty. The new node is the root node
    if (y == None):
        y = newnode
 
    # If the new key is less than the leaf node key
    # Assign the new node to be its left child
    elif (key < y.key):
        y.left = newnode
 
    # else assign the new node its
    # right child
    else:
        y.right = newnode
 
    # Returns the pointer where the
    # new node is inserted
    return y
 
# A utility function to do inorder
# traversal of BST
def Inorder(root) :
 
    if (root == None) :
        return
    else:
        Inorder(root.left)
        print( root.key, end = " " )
        Inorder(root.right)
                         
# Driver Code
if __name__ == '__main__':
 
    """ Let us create following BST
            50
        / \
        30     70
        / \ / \
    20 40 60 80 """
 
    root = None
    root = insert(root, 50)
    insert(root, 30)
    insert(root, 20)
    insert(root, 40)
    insert(root, 70)
    insert(root, 60)
    insert(root, 80)
 
    # Pr inorder traversal of the BST
    Inorder(root)
 
# This code is contributed by
# SHUBHAMSINGH10

// C# program to demonstrate insert 
// operation in binary search tree
using System;
 
class GFG
{
    // BST node
    class Node
    {
        public int key;
        public Node left, right;
    };
 
    // Utility function to create a new node
    static Node newNode(int data)
    {
        Node temp = new Node();
 
        temp.key = data;
 
        temp.left = null;
        temp.right = null;
 
        return temp;
    }
 
    // A utility function to insert a new
    // Node with given key in BST
    static Node insert(Node root, int key)
    {
        // Create a new Node containing
        // the new element
        Node newnode = newNode(key);
 
        // Pointer to start traversing from root and
        // traverses downward path to search
        // where the new node to be inserted
        Node x = root;
 
        // Pointer y maintains the trailing
        // pointer of x
        Node y = null;
 
        while (x != null)
        {
            y = x;
            if (key < x.key)
                x = x.left;
            else
                x = x.right;
        }
 
        // If the root is null i.e the tree is empty
        // The new node is the root node
        if (y == null)
            y = newnode;
 
        // If the new key is less than the leaf node key
        // Assign the new node to be its left child
        else if (key < y.key)
            y.left = newnode;
 
        // else assign the new node its right child
        else
            y.right = newnode;
 
        // Returns the pointer where the
        // new node is inserted
        return y;
    }
 
    // A utility function to do inorder
    // traversal of BST
    static void Inorder(Node root)
    {
        if (root == null)
            return;
        else
        {
            Inorder(root.left);
            Console.Write( root.key +" ");
            Inorder(root.right);
        }
    }
 
    // Driver code
    public static void Main(String []args)
    {
        /* Let us create following BST
                50
            / \
            30 70
            / \ / \
        20 40 60 80 */
 
        Node root = null;
        root = insert(root, 50);
        insert(root, 30);
        insert(root, 20);
        insert(root, 40);
        insert(root, 70);
        insert(root, 60);
        insert(root, 80);
 
        // Print inorder traversal of the BST
        Inorder(root);
    }
}
 
// This code is contributed 29AjayKumar

<script>
 
// javascript program to demonstrate insert 
// operation in binary search tree
// BST node
class Node
{
    constructor()
    {
        this.key = 0;
        this.left = null;
        this.right = null;
    }
};
 
// Utility function to create a new node
function newNode(data)
{
    var temp = new Node();
    temp.key = data;
    temp.left = null;
    temp.right = null;
    return temp;
}
 
// A utility function to insert a new
// Node with given key in BST
function insert(root, key)
{
 
    // Create a new Node containing
    // the new element
    var newnode = newNode(key);
     
    // Pointer to start traversing from root and
    // traverses downward path to search
    // where the new node to be inserted
    var x = root;
     
    // Pointer y maintains the trailing
    // pointer of x
    var y = null;
 
    while (x != null)
    {
        y = x;
        if (key < x.key)
            x = x.left;
        else
            x = x.right;
    }
     
    // If the root is null i.e the tree is empty
    // The new node is the root node
    if (y == null)
        y = newnode;
         
    // If the new key is less than the leaf node key
    // Assign the new node to be its left child
    else if (key < y.key)
        y.left = newnode;
         
    // else assign the new node its right child
    else
        y.right = newnode;
         
    // Returns the pointer where the
    // new node is inserted
    return y;
}
 
// A utility function to do inorder
// traversal of BST
function Inorder(root)
{
    if (root == null)
        return;
    else
    {
        Inorder(root.left);
        document.write( root.key +" ");
        Inorder(root.right);
    }
}
 
// Driver code
/* Let us create following BST
        50
    / \
    30 70
    / \ / \
20 40 60 80 */
var root = null;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
// Print inorder traversal of the BST
Inorder(root);
 
// This code is contributed by itsok.
</script>

20 30 40 50 60 70 80

Análisis de Complejidad: 
 

• Complejidad temporal: O(h), donde h es la altura del árbol de búsqueda binaria. En el peor de los casos, la altura es igual al número de Nodes.

• Complejidad espacial: O(1), no se requiere espacio extra.