Insertion in Binary Search Tree

Category: Data Structures
Tags: #datastructures#tree#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.

Insertion in binary search tree

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

  1. Start at the root node.
  2. If the new node's value is less than the current node's value, move to the left subtree.
  3. If the new node's value is greater than the current node's value, move to the right subtree.
  4. Repeat steps 2 and 3 until we reach a leaf node.
  5. 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.

Insertion in binary search tree steps

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

6
3
2
1
4
9
8
10

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.


Recommended Posts