Insertion in Binary Search Tree (BST)

Namachila 3 days ago

0 0 11 minutes read

Given a BST, the task is to insert a new node in this BST.

Example:

Insertion in Binary Search Tree

How to Insert a value in a Binary Search Tree:

A new key is always inserted at the leaf by maintaining the property of the binary search tree. We start searching for a key from the root until we hit a leaf node. Once a leaf node is found, the new node is added as a child of the leaf node. The below steps are followed while we try to insert a node into a binary search tree:

Check the value to be inserted (say X) with the value of the current node (say val) we are in:
- If X is less than val move to the left subtree.
- Otherwise, move to the right subtree.
Once the leaf node is reached, insert X to its right or left based on the relation between X and the leaf node’s value.

Follow the below illustration for a better understanding:

Illustration:

Insertion in BST

Insertion in BST

Insertion in BST

Insertion in BST

Insertion in BST

Insertion in Binary Search Tree using Recursion:

Below is the implementation of the insertion operation using recursion.

C++14

// C++ program to demonstrate insertion
// in a BST recursively
 
#include <bits/stdc++.h>
using namespace std;
 
class BST {
    int data;
    BST *left, *right;
 
public:
    // Default constructor.
    BST();
 
    // Parameterized constructor.
    BST(int);
 
    // Insert function.
    BST* Insert(BST*, int);
 
    // Inorder traversal.
    void Inorder(BST*);
};
 
// Default Constructor definition.
BST::BST()
    : data(0)
    , left(NULL)
    , right(NULL)
{
}
 
// Parameterized Constructor definition.
BST::BST(int value)
{
    data = value;
    left = right = NULL;
}
 
// Insert function definition.
BST* BST::Insert(BST* root, int value)
{
    if (!root) {
 
        // Insert the first node, if root is NULL.
        return new BST(value);
    }
 
    // Insert data.
    if (value > root->data) {
        // Insert right node data, if the 'value'
        // to be inserted is greater than 'root' node data.
 
        // Process right nodes.
        root->right = Insert(root->right, value);
    }
    else if (value < root->data) {
        // Insert left node data, if the 'value'
        // to be inserted is smaller than 'root' node data.
 
        // Process left nodes.
        root->left = Insert(root->left, value);
    }
 
    // Return 'root' node, after insertion.
    return root;
}
 
// Inorder traversal function.
// This gives data in sorted order.
void BST::Inorder(BST* root)
{
    if (!root) {
        return;
    }
    Inorder(root->left);
    cout << root->data << " ";
    Inorder(root->right);
}
 
// Driver code
int main()
{
    BST b, *root = NULL;
    root = b.Insert(root, 50);
    b.Insert(root, 30);
    b.Insert(root, 20);
    b.Insert(root, 40);
    b.Insert(root, 70);
    b.Insert(root, 60);
    b.Insert(root, 80);
 
    b.Inorder(root);
    return 0;
}

C

// C program to demonstrate insert
// operation in binary
// search tree.
 
#include <stdio.h>
#include <stdlib.h>
 
struct node {
    int key;
    struct node *left, *right;
};
 
// A utility function to create a new BST node
struct node* newNode(int item)
{
    struct node* temp
        = (struct node*)malloc(sizeof(struct node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}
 
// A utility function to do inorder traversal of BST
void inorder(struct node* root)
{
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->key);
        inorder(root->right);
    }
}
 
// A utility function to insert
// a new node with given key in BST
struct node* insert(struct node* node, int key)
{
    // If the tree is empty, return a new node
    if (node == NULL)
        return newNode(key);
 
    // Otherwise, recur down the tree
    if (key < node->key)
        node->left = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);
 
    // Return the (unchanged) node pointer
    return node;
}
 
// Driver Code
int main()
{
    /* Let us create following BST
              50
           /     \
          30      70
         /  \    /  \
       20   40  60   80 */
    struct 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

// Java program to demonstrate
// insert operation in binary
// search tree
 
import java.io.*;
 
public class BinarySearchTree {
 
    // Class containing left
    // and right child of current node
    // and key value
    class Node {
        int key;
        Node left, right;
 
        public Node(int item)
        {
            key = item;
            left = right = null;
        }
    }
 
    // Root of BST
    Node root;
 
    // Constructor
    BinarySearchTree() { root = null; }
 
    BinarySearchTree(int value) { root = new Node(value); }
 
    // This method mainly calls insertRec()
    void insert(int key) { root = insertRec(root, key); }
 
    // A recursive function to
    // insert a new key in BST
    Node insertRec(Node root, int key)
    {
        // If the tree is empty,
        // return a new node
        if (root == null) {
            root = new Node(key);
            return root;
        }
 
        // Otherwise, recur down the tree
        else if (key < root.key)
            root.left = insertRec(root.left, key);
        else if (key > root.key)
            root.right = insertRec(root.right, key);
 
        // Return the (unchanged) node pointer
        return root;
    }
 
    // This method mainly calls InorderRec()
    void inorder() { inorderRec(root); }
 
    // A utility function to
    // do inorder traversal of BST
    void inorderRec(Node root)
    {
        if (root != null) {
            inorderRec(root.left);
            System.out.print(root.key + " ");
            inorderRec(root.right);
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        BinarySearchTree tree = new BinarySearchTree();
 
        /* Let us create following BST
              50
           /     \
          30      70
         /  \    /  \
       20   40  60   80 */
        tree.insert(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);
 
        // Print inorder traversal of the BST
        tree.inorder();
    }
}
 
// This code is contributed by Ankur Narain Verma

Python3

# Python program to demonstrate
# insert operation in binary search tree
 
 
# A utility class that represents
# an individual node in a BST
class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key
 
 
# A utility function to insert
# a new node with the given key
def insert(root, key):
    if root is None:
        return Node(key)
    else:
        if root.val == key:
            return root
        elif root.val < key:
            root.right = insert(root.right, key)
        else:
            root.left = insert(root.left, key)
    return root
 
 
# A utility function to do inorder tree traversal
def inorder(root):
    if root:
        inorder(root.left)
        print(root.val, end=" ")
        inorder(root.right)
 
 
# Driver program to test the above functions
if __name__ == '__main__':
 
    # Let us create the following BST
    # 50
    #  /     \
    # 30     70
    #  / \ / \
    # 20 40 60 80
 
    r = Node(50)
    r = insert(r, 30)
    r = insert(r, 20)
    r = insert(r, 40)
    r = insert(r, 70)
    r = insert(r, 60)
    r = insert(r, 80)
 
    # Print inorder traversal of the BST
    inorder(r)

C#

// C# program to demonstrate
// insert operation in binary
// search tree
 
using System;
 
class BinarySearchTree {
 
    // Class containing left and
    // right child of current node
    // and key value
    public class Node {
        public int key;
        public Node left, right;
 
        public Node(int item)
        {
            key = item;
            left = right = null;
        }
    }
 
    // Root of BST
    Node root;
 
    // Constructor
    BinarySearchTree() { root = null; }
 
    BinarySearchTree(int value) { root = new Node(value); }
 
    // This method mainly calls insertRec()
    void insert(int key) { root = insertRec(root, key); }
 
    // A recursive function to insert
    // a new key in BST
    Node insertRec(Node root, int key)
    {
 
        // If the tree is empty,
        // return a new node
        if (root == null) {
            root = new Node(key);
            return root;
        }
 
        // Otherwise, recur down the tree
        if (key < root.key)
            root.left = insertRec(root.left, key);
        else if (key > root.key)
            root.right = insertRec(root.right, key);
 
        // Return the (unchanged) node pointer
        return root;
    }
 
    // This method mainly calls InorderRec()
    void inorder() { inorderRec(root); }
 
    // A utility function to
    // do inorder traversal of BST
    void inorderRec(Node root)
    {
        if (root != null) {
            inorderRec(root.left);
            Console.Write(root.key + " ");
            inorderRec(root.right);
        }
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        BinarySearchTree tree = new BinarySearchTree();
 
        /* Let us create following BST
              50
           /     \
          30      70
         /  \    /  \
       20   40  60   80 */
        tree.insert(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);
 
        // Print inorder traversal of the BST
        tree.inorder();
    }
}
 
// This code is contributed by aashish1995

Javascript

<script>
// javascript program to demonstrate 
// insert operation in binary
// search tree
    /*
     * Class containing left and right child of current node and key value
     */
    class Node {
     
constructor(item) {
            this.key = item;
            this.left = this.right = null;
        }
    }
 
    // Root of BST
    var root = null;
 
    // This method mainly calls insertRec()
    function insert(key) {
        root = insertRec(root, key);
    }
 
    // A recursive function to insert a new key in BST
    function insertRec(root, key) {
 
        // If the tree is empty, return a new node
        if (root == null) {
            root = new Node(key);
            return root;
        }
 
        // Otherwise, recur down the tree
        if (key < root.key)
            root.left = insertRec(root.left, key);
        else if (key > root.key)
            root.right = insertRec(root.right, key);
 
        // Return the (unchanged) node pointer
        return root;
    }
 
    // This method mainly calls InorderRec()
    function inorder() {
        inorderRec(root);
    }
 
    // A utility function to
    // do inorder traversal of BST
    function inorderRec(root)
    {
        if (root != null) {
            inorderRec(root.left);
            document.write(root.key+"<br/>");
            inorderRec(root.right);
        }
    }
 
// Driver Code
 
        /* Let us create following BST
              50
           /     \
          30      70
         /  \    /  \
       20   40  60   80 */
        insert(50);
        insert(30);
        insert(20);
        insert(40);
        insert(70);
        insert(60);
        insert(80);
 
        // Print inorder traversal of the BST
        inorder();
 
// This code is contributed by Rajput-Ji
</script>

Output

20 30 40 50 60 70 80

Time Complexity:

The worst-case time complexity of insert operations is O(h) where h is the height of the Binary Search Tree.
In the worst case, we may have to travel from the root to the deepest leaf node. The height of a skewed tree may become n and the time complexity of insertion operation may become O(n).

Auxiliary Space: The auxiliary space complexity of insertion into a binary search tree is O(1)

Insertion in Binary Search Tree using Iterative approach:

Instead of using recursion, we can also implement the insertion operation iteratively using a while loop. Below is the implementation using a while loop.

C++

// C++ Code to insert node and to print inorder traversal
// using iteration
 
#include <bits/stdc++.h>
using namespace std;
 
// BST Node
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node(int val)
        : val(val)
        , left(NULL)
        , right(NULL)
    {
    }
};
 
// Utility function to insert node in BST
void insert(Node*& root, int key)
{
    Node* node = new Node(key);
    if (!root) {
        root = node;
        return;
    }
    Node* prev = NULL;
    Node* temp = root;
    while (temp) {
        if (temp->val > key) {
            prev = temp;
            temp = temp->left;
        }
        else if (temp->val < key) {
            prev = temp;
            temp = temp->right;
        }
    }
    if (prev->val > key)
        prev->left = node;
    else
        prev->right = node;
}
 
// Utility function to print inorder traversal
void inorder(Node* root)
{
    Node* temp = root;
    stack<Node*> st;
    while (temp != NULL || !st.empty()) {
        if (temp != NULL) {
            st.push(temp);
            temp = temp->left;
        }
        else {
            temp = st.top();
            st.pop();
            cout << temp->val << " ";
            temp = temp->right;
        }
    }
}
 
// Driver code
int main()
{
    Node* root = NULL;
    insert(root, 30);
    insert(root, 50);
    insert(root, 15);
    insert(root, 20);
    insert(root, 10);
    insert(root, 40);
    insert(root, 60);
 
    // Function call to print the inorder traversal
    inorder(root);
 
    return 0;
}

Java

// Java code to implement the insertion
// in binary search tree
 
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Driver code
    public static void main(String[] args)
    {
        BST tree = new BST();
        tree.insert(30);
        tree.insert(50);
        tree.insert(15);
        tree.insert(20);
        tree.insert(10);
        tree.insert(40);
        tree.insert(60);
 
        tree.inorder();
    }
}
 
class Node {
    Node left;
    int val;
    Node right;
    Node(int val) { this.val = val; }
}
 
class BST {
    Node root;
 
    // Function to insert a key
    public void insert(int key)
    {
        Node node = new Node(key);
        if (root == null) {
            root = node;
            return;
        }
        Node prev = null;
        Node temp = root;
        while (temp != null) {
            if (temp.val > key) {
                prev = temp;
                temp = temp.left;
            }
            else if (temp.val < key) {
                prev = temp;
                temp = temp.right;
            }
        }
        if (prev.val > key)
            prev.left = node;
        else
            prev.right = node;
    }
 
    // Function to print the inorder value
    public void inorder()
    {
        Node temp = root;
        Stack<Node> stack = new Stack<>();
        while (temp != null || !stack.isEmpty()) {
            if (temp != null) {
                stack.add(temp);
                temp = temp.left;
            }
            else {
                temp = stack.pop();
                System.out.print(temp.val + " ");
                temp = temp.right;
            }
        }
    }
}

Python3

# Python 3 code to implement the insertion
# operation iteratively
 
 
class GFG:
    @staticmethod
    def main(args):
        tree = BST()
        tree.insert(30)
        tree.insert(50)
        tree.insert(15)
        tree.insert(20)
        tree.insert(10)
        tree.insert(40)
        tree.insert(60)
        tree.inorder()
 
 
class Node:
    left = None
    val = 0
    right = None
 
    def __init__(self, val):
        self.val = val
 
 
class BST:
    root = None
 
    # Function to insert a key in the BST
    def insert(self, key):
        node = Node(key)
        if (self.root == None):
            self.root = node
            return
        prev = None
        temp = self.root
        while (temp != None):
            if (temp.val > key):
                prev = temp
                temp = temp.left
            elif(temp.val < key):
                prev = temp
                temp = temp.right
        if (prev.val > key):
            prev.left = node
        else:
            prev.right = node
 
    # Function to print the inorder traversal of BST
 
    def inorder(self):
        temp = self.root
        stack = []
        while (temp != None or not (len(stack) == 0)):
            if (temp != None):
                stack.append(temp)
                temp = temp.left
            else:
                temp = stack.pop()
                print(str(temp.val) + " ", end="")
                temp = temp.right
 
 
if __name__ == "__main__":
    GFG.main([])
 
 
# This code is contributed by rastogik346.

C#

// Function to implement the insertion
// operation iteratively
 
using System;
using System.Collections.Generic;
 
public class GFG {
 
    // Driver code
    public static void Main(String[] args)
    {
        BST tree = new BST();
        tree.insert(30);
        tree.insert(50);
        tree.insert(15);
        tree.insert(20);
        tree.insert(10);
        tree.insert(40);
        tree.insert(60);
 
        // Function call to print the inorder traversal
        tree.inorder();
    }
}
 
public class Node {
    public Node left;
    public int val;
    public Node right;
 
    public Node(int val) { this.val = val; }
}
 
public class BST {
    public Node root;
 
    // Function to insert a new key in the BST
    public void insert(int key)
    {
        Node node = new Node(key);
        if (root == null) {
            root = node;
            return;
        }
        Node prev = null;
        Node temp = root;
        while (temp != null) {
            if (temp.val > key) {
                prev = temp;
                temp = temp.left;
            }
            else if (temp.val < key) {
                prev = temp;
                temp = temp.right;
            }
        }
        if (prev.val > key)
            prev.left = node;
        else
            prev.right = node;
    }
 
    // Function to print the inorder traversal of BST
    public void inorder()
    {
        Node temp = root;
        Stack<Node> stack = new Stack<Node>();
        while (temp != null || stack.Count != 0) {
            if (temp != null) {
                stack.Push(temp);
                temp = temp.left;
            }
            else {
                temp = stack.Pop();
                Console.Write(temp.val + " ");
                temp = temp.right;
            }
        }
    }
}
 
// This code is contributed by Rajput-Ji

Javascript

// JavaScript code to implement the insertion
// in binary search tree
 
class Node {
  constructor(val) {
    this.left = null;
    this.val = val;
    this.right = null;
  }
}
 
class BST {
  constructor() {
    this.root = null;
  }
 
  // Function to insert a key
  insert(key) {
    let node = new Node(key);
    if (this.root == null) {
      this.root = node;
      return;
    }
    let prev = null;
    let temp = this.root;
    while (temp != null) {
      if (temp.val > key) {
        prev = temp;
        temp = temp.left;
      } else if (temp.val < key) {
        prev = temp;
        temp = temp.right;
      }
    }
    if (prev.val > key) prev.left = node;
    else prev.right = node;
  }
 
  // Function to print the inorder value
  inorder() {
    let temp = this.root;
    let stack = [];
    while (temp != null || stack.length > 0) {
      if (temp != null) {
        stack.push(temp);
        temp = temp.left;
      } else {
        temp = stack.pop();
        console.log(temp.val + " ");
        temp = temp.right;
      }
    }
  }
}
 
let tree = new BST();
tree.insert(30);
tree.insert(50);
tree.insert(15);
tree.insert(20);
tree.insert(10);
tree.insert(40);
tree.insert(60);
 
tree.inorder();
// this code is contributed by devendrasolunke

Output

10 15 20 30 40 50 60

The time complexity of inorder traversal is O(n), as each node is visited once.
The Auxiliary space is O(n), as we use a stack to store nodes for recursion.

Related Links:

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!