Insert a node in Binary Search Tree Iteratively

Iterative Method

To insert the node into the binary search tree, we need to compare the node with the tree’s root. If the node is greater than the root value, we move to the right side of the binary search tree; otherwise, we move to the left side of the binary search tree. We will follow this process until we reach any leaf value, then we create a new node and attach it to the leaf of the tree. A condition that needs to handle when the tree is empty, the node is made the root of the binary search tree. Therefore we insert a node in the binary search tree. 

Algorithm

1. We will create a new node with the given value. 
2. To insert the node in BST, compare it with the root node.
3. If the node is greater than the root node, move to the right subtree, otherwise proceed to the left subtree. 
4. Follow this process until we reach the leaf node.
5. Now we will attach the node with the leaf node; if the value of a node is greater than the leaf node, it will attach to the right side of the leaf node. Otherwise, it will attach to the left side of the leaf node. 
6. The base case needs to be handled separately, i.e., if the BST is empty, the node to be inserted will become the root of the current BST.

Implementation in C++

// C++ program to demonstrate 
// insert a node in the binary search tree
#include <bits/stdc++.h>
using namespace std;

// BST node
class Node {
    public:
        int value;
        Node *left, *right;
        Node(int value){
            this->value = value;
            left = NULL;
            right = NULL;
        }
};

// A utility function to insert a new
// Node with given value in BST
Node* insert(Node* root, int value)
{
    // Create a new Node containing
    // the new element
    Node* newnode = new Node(value);

    // Pointer to start iterating the array
    // from the root node
    Node* curr = root;

    // prev pointer will note the trailing of start pointer
    Node* prev = NULL;

    while (curr!= NULL) {
        prev = curr;
        if (value < curr->value)
            curr = curr->left;
        else
            curr = curr->right;
    }

    // If the prev is NULL it means that the tree is empty
    // The new node is the root node
    if (prev == NULL)
        prev = newnode;

    // if the new value is lesser than the leaf node
    // make the newNode as the left child of leaf node
    else if (value < prev->value)
        prev->left = newnode;

    // otherwise make the newNode as right child of leaf node
    else
        prev->right = newnode;

    // Returns the prev pointer
    // where we have inserted the newNode
    return prev;
}

void InorderTraversal(Node *root){
    // if the root node is NULL
    if(!root)
        return;
    // recursively call for left subtree
    InorderTraversal(root->left);
    // print the current root value
    cout << root->value << " ";
    // recursively call for the right subtree
    InorderTraversal(root->right);
    return;
}

// Driver code
int main()
{
    // Let us create the BST given in sample example 1

    Node* root = NULL;
    root = insert(root, 50);
    insert(root, 28);
    insert(root, 52);
    insert(root, 26);
    insert(root, 45);
    insert(root, 56);

    // Print inorder traversal of the BST
    cout << "Inorder Traversal of BST before inserting the Node ";
    InorderTraversal(root);
    cout << endl;
    // Node to be inserted is 51
    insert(root, 51);

    cout << "Inorder Traversal of BST after inserting the Node ";
    InorderTraversal(root);

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output: 

Inorder Traversal of BST before inserting the Node 26 28 45 50 52 56 
Inorder Traversal of BST after inserting the Node 26 28 45 50 51 52 56

Complexity Analysis

Time Complexity: O(H)

Explanation: H is the height of the binary search tree because we will travel at most height for any particular node, but in the worst-case, height can be equal to the N, (where N is the total number of nodes), to insert a node in the binary search tree. For Ex: when we insert the node in Ascending or descending order, the height of the tree is equal to the number of nodes of the tree. 

Space Complexity: O(1)

Explanation: We are just constants; it will not be considered extra Space. Their time complexity is O(1). 

Check out this problem - Diameter Of Binary Tree.

Must Read Recursive Binary Search.

Frequently Asked Questions

What is the difference between a binary tree and a binary search tree?

A tree having a maximum of 2 children is called a binary tree, whereas a binary search tree is a particular binary tree having the following properties. 

Keys in the left subtree are always smaller than the root’s node, whereas keys in the right subtree are greater than the root’s node. 

What is inorder traversal ? 

In inorder traversal, we first traverse the left subtree, then visit the root and then traverse the right subtree. 

How to get the sorted output from the binary search tree? 

Traversing the binary search tree in the inorder traversal gives us the sorted output. 

Conclusion

This article discussed the iterative approach to inserting a node in the binary search tree. 

Recommended Reading

• Operations on Binary Search Tree
• Insertion in Binary Tree
• Difference Between Binary Tree and Binary Search Tree

We hope you understand the problem and solution properly. Now you can do more similar questions on BST in an iterative manner. 

Check out some of the amazing Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Basics of C, Basics of Java, etc. along with some Contests and Interview Experiences only on Coding Ninjas Studio. 

Thank you for reading. 

Until then, Keep Learning and Keep Coding.