Algotree > Algorithms > Tree & Graph Traversal > Binary Search Tree > Inserting Into A Binary Search Tree

Inserting Into A Binary Search Tree

Inserting into a BST The logic behind inserting a node into a BST is as follows:

In a binary search tree,
- Left child of a parent node < Parent node
- Right child of a parent > Parent node.
Based on the above criteria, we traverse the BST by comparing the node to be inserted with the root (parent),
- We go to the left if the node to be inserted is less than the parent.
- We go to the right if the node to be inserted is greater than the parent.
- If a nullptr is found during the traversal, we inserted the node.

Time complexity of inserting a node into a BST with N nodes :
Worst-case time complexity is O ( N ), if the tree is linear; i.e to insert into a BST that is linear (unbalanced) all the nodes will have to be traversed and compared.
Best-case time complexity is O ( log N ), if the tree is balanced, i.e for a balanced BST the height would be log N, and hence log N comparisons would be needed before a right place is found for inserting the node.

C++ : Program for inserting a node into a BST

#include<iostream>
#include<vector>
using namespace std;

class Node {

    public:
    int data;
    Node * left;
    Node * right;
    Node(int x) : data(x), left(NULL), right(NULL)
    {}
    Node(int x, Node* left_node, Node* right_node) : data(x), left(left_node), right(right_node)
    {}
};

class Tree {

    public:

    vector<int> order;

    /* The in-order traversal of a valid BST 
       is always in increasing order (sorted) */
    void InOrder (Node * node) {

        if (node != NULL) {
            InOrder(node->left);
            cout << node->data << " ";
            order.push_back(node->data);
            InOrder(node->right);
        }
    }

    Node * InsertIntoBST (Node * root, Node * k) {
        if (root == NULL) {
            root = k;
        } else if (root->data < k->data) {
            root->right = InsertIntoBST(root->right, k);
        } else if (root->data > k->data) {
            root->left = InsertIntoBST(root->left, k);
        }
        return root;
    }
};

int main() {

    /*   4 
        / \
       2   9  */

    Node node2(2), node9(9);
    Node root_node4(4, &node2, &node9);
    Node node5(5); // Node to be inserted.

    Tree t;
    cout << "Before inserting node (5) : ";
    t.InOrder(&root_node4);
    Node * root = t.InsertIntoBST(&root_node4, &node5);
    cout << "\nAfter inserting node (5) : ";
    t.InOrder(&root_node4);

    /*   3 
        / \
       1   7  
            \
             8  */

    Node node1(1), node8(8);
    Node node7(7, nullptr, &node8);
    Node root_node3(3, &node1, &node7);
    Node node6(6); //Node to be inserted.

    cout << "\n\nBefore Inserting node (6) : ";
    t.InOrder(&root_node3);
    root = t.InsertIntoBST(&root_node3, &node6);
    cout << "\nAfter Inserting node (6) : ";
    t.InOrder(&root_node3);

    return 0;
}

Output

Before inserting node (5) : 2 4 9 
After inserting node (5) : 2 4 5 9 

Before Inserting node (6) : 1 3 7 8 
After Inserting node (6) : 1 3 6 7 8