Insert a node in Binary Search Tree Iteratively

Vaibhav Agarwal
Last Updated: May 13, 2022

Introduction

This article will discuss the iterative approach to insert a node in the binary search tree. Let’s first recap what is Binary search tree in brief and sources to study more about it. 

Binary Search Tree

A binary Search Tree is a particular type of binary tree in which keys in the left subtree are always smaller than the root node, and nodes in the right subtree are always greater than the root node. To know more about the Binary search tree, you can refer to this.  

Sample Examples

Input: Insert node 51 into the given binary search Tree. 

Output:

 

ExplanationThe node with a value  51 would be inserted in the right subtree of the root node, i.e., 50, and as the left child of node 52 as 52 > 51. Hence we insert a node in the binary search tree. 

 

Input: Insert node 26 into the given binary search Tree. 

Output

ExplanationThe node with a value  26 would be inserted in the right subtree of the root node, i.e., 15, we move to the right subtree, now 50 > 26, we will move to the left subtree, and finally 23<26, therefore we will attach 26 as the left child of 23. Hence we insert a node in the binary search tree. 

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

 

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 ComplexityO(1)

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

Frequently asked questions

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

Ans. A tree having a maximum of 2 children is called a binary tree, whereas 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. 

 

Q2. What is inorder traversal ? 

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

 

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

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

Key takeaways

This article discussed the iterative approach to insert a node in the 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. 

If you are a beginner, interested in coding, and want to learn DSA, you can look for our guided path for DSA, which is free! 

Thank you for reading. 

Until then, Keep Learning and Keep Coding.

Was this article helpful ?
2 upvotes

Comments

No comments yet

Be the first to share what you think