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

Inserting Into A Binary Search Tree

The logic behind inserting a node into a binary search tree is as follows:

In a binary search tree, the left child of a parent node is always less than the parent and the right child of a parent is always greater than the parent. Thus we traverse comparing the node to be inserted with the root and all the ways down the tree till an appropriate position is found for the node in the tree.

Time complexity of inserting a node into a binary search tree with N nodes :
Worst-case time complexity is O(N), if the tree is linear; i.e to insert into a binary search tree 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 binary search tree the height would be log N and hence log N comparision before a right place is found for the node to be inserted.

C++ : Inserting into a binary search tree. Implemented in C++11

#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)
    {}
};

class Tree {

    public:

    vector<int> order;

    /* The in-order traversal of a valid binary search tree 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, int data) {
        if (root == NULL) {
            root = new Node(data);
        } else if (root->data < data) {
            root->right = InsertIntoBST(root->right, data);
        } else if (root->data > data) {
            root->left = InsertIntoBST(root->left, data);
        }
        return root;
    }
};

int main() {

    /*   6 
        / \
       4   9  */

    Node * root1 = new Node(6);
    root1->left = new Node(4);
    root1->right = new Node(9);

    Tree t;
    cout << "Before Inserting 5 : ";
    t.InOrder(root1);
    root1 = t.InsertIntoBST(root1, 5);
    cout << "\nAfter Inserting 5 : ";
    t.InOrder(root1);

    /*   5
        / \
       1   7  
            \
             8  */
    Node * root2 = new Node(5);
    root2->left = new Node(1);
    root2->right = new Node(7);
    root2->right->right = new Node(8);

    cout << "\n\nBefore Inserting 6 : ";
    t.InOrder(root2);
    root1 = t.InsertIntoBST(root2, 6);
    cout << "\nAfter Inserting 6 : ";
    t.InOrder(root2);

    /*   2 
        / 
       1   */
    Node * root3 = new Node(2);
    root3->left = new Node(1);

    cout << "\n\nBefore Inserting 4 : ";
    t.InOrder(root3);
    root1 = t.InsertIntoBST(root3, 4);
    cout << "\nAfter Inserting 4 : ";
    t.InOrder(root3);

    return 0;
}

Output of validating a binary search tree implemented in C++11

Before Inserting 5 : 4 6 9 
After Inserting 5 : 4 5 6 9 

Before Inserting 6 : 1 5 7 8 
After Inserting 6 : 1 5 6 7 8 

Before Inserting 4 : 1 2 
After Inserting 4 : 1 2 4