# Inserting Into A Binary Search Tree

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
``````