Insertion in Binary Search Tree

Given a Binary Search Tree (BST) insert a new node in BST. Insertion in the binary search tree is always done as a leaf node. We have to traverse the binary search tree and find the right position for the new node based on its value by comparing all other nodes.

To insert a node into a BST, we follow these steps:

Start at the root node.
If the new node's value is less than the current node's value, move to the left subtree.
If the new node's value is greater than the current node's value, move to the right subtree.
Repeat steps 2 and 3 until we reach a leaf node.
Insert the new node as the child of the leaf node.

If the root node is null in that case the new node will become the root node otherwise we have to find the correct position of new node and insert it.

Python

class Node:
    def __init__(self, data):
        self.left = None
        self.data = data
        self.right = None

def insert_node(node, value):
    if node is None:
        return Node(value)

    if value < node.data:
        node.left = insert_node(node.left, value)
    else:
        node.right = insert_node(node.right, value)

    return node

def pre_order(root):
    if root:
        print(root.data)
        pre_order(root.left)
        pre_order(root.right)


# Manually creating tree
root = Node(6)
root.left = Node(3)
root.right = Node(9)
root.left.left = Node(2)
root.left.right = Node(4)
root.right.left = Node(8)
root.right.right = Node(10)

# insertion of new node
root = insert_node(root, 1)
pre_order(root)

JavaScript

class Node {
    constructor(data) {
        this.left = null;
        this.data = data;
        this.right = null;
    }
}

function insertNode(node, value) {
    if (node === null) {
        return new Node(value);
    }

    if (value < node.data) {
        node.left = insertNode(node.left, value);
    } else {
        node.right = insertNode(node.right, value);
    }

    return node;
}

function preOrder(root) {
    if (root !== null) {
        console.log(root.data);
        preOrder(root.left);
        preOrder(root.right);
    }
}

// Manually creating tree
let root = new Node(6);
root.left = new Node(3);
root.right = new Node(9);
root.left.left = new Node(2);
root.left.right = new Node(4);
root.right.left = new Node(8);
root.right.right = new Node(10);

// Insertion of a new node
root = insertNode(root, 1);
preOrder(root);

Java

class Node {
    Node left, right;
    int data;

    Node(int data) {
        this.left = null;
        this.data = data;
        this.right = null;
    }
}

public class Main {
    public static Node insertNode(Node node, int value) {
        if (node == null) {
            return new Node(value);
        }

        if (value < node.data) {
            node.left = insertNode(node.left, value);
        } else {
            node.right = insertNode(node.right, value);
        }

        return node;
    }

    public static void preOrder(Node root) {
        if (root != null) {
            System.out.println(root.data);
            preOrder(root.left);
            preOrder(root.right);
        }
    }

    public static void main(String[] args) {
        // Manually creating tree
        Node root = new Node(6);
        root.left = new Node(3);
        root.right = new Node(9);
        root.left.left = new Node(2);
        root.left.right = new Node(4);
        root.right.left = new Node(8);
        root.right.right = new Node(10);

        // Insertion of a new node
        root = insertNode(root, 1);
        preOrder(root);
    }
}

C++

#include <iostream>

class Node {
public:
    Node *left, *right;
    int data;

    Node(int data) {
        this->left = nullptr;
        this->data = data;
        this->right = nullptr;
    }
};

Node* insertNode(Node* node, int value) {
    if (node == nullptr) {
        return new Node(value);
    }

    if (value < node->data) {
        node->left = insertNode(node->left, value);
    } else {
        node->right = insertNode(node->right, value);
    }

    return node;
}

void preOrder(Node* root) {
    if (root != nullptr) {
        std::cout << root->data << std::endl;
        preOrder(root->left);
        preOrder(root->right);
    }
}

int main() {
    // Manually creating tree
    Node* root = new Node(6);
    root->left = new Node(3);
    root->right = new Node(9);
    root->left->left = new Node(2);
    root->left->right = new Node(4);
    root->right->left = new Node(8);
    root->right->right = new Node(10);

    // Insertion of a new node
    root = insertNode(root, 1);
    preOrder(root);

    return 0;
}

package main

import "fmt"

type Node struct {
	left  *Node
	data  int
	right *Node
}

func insertNode(node *Node, value int) *Node {
	if node == nil {
		return &Node{nil, value, nil}
	}

	if value < node.data {
		node.left = insertNode(node.left, value)
	} else {
		node.right = insertNode(node.right, value)
	}

	return node
}

func preOrder(root *Node) {
	if root != nil {
		fmt.Println(root.data)
		preOrder(root.left)
		preOrder(root.right)
	}
}

func main() {
	// Manually creating tree
	root := &Node{nil, 6, nil}
	root.left = &Node{nil, 3, nil}
	root.right = &Node{nil, 9, nil}
	root.left.left = &Node{nil, 2, nil}
	root.left.right = &Node{nil, 4, nil}
	root.right.left = &Node{nil, 8, nil}
	root.right.right = &Node{nil, 10, nil}

	// Insertion of a new node
	root = insertNode(root, 1)
	preOrder(root)
}

Output

Time complexity

The time complexity of the binary search tree insertion algorithm in all the languages you provided is O(log n), where n is the number of nodes in the BST.
We can also say it as O(h) where h is the height of a Binary search tree which is generally log n.
In worst case it could be O(n) if the Binary search tree is skewed.

Space Complexity

The space complexity of the binary search tree insertion algorithm in all the languages you provided is O(1).

This means that the algorithm does not require any additional space to be allocated, other than the space required to store the nodes of the BST.

Insertion in Binary Search Tree

Time complexity

Space Complexity

Recommended Posts