The logic behind inserting a node into a binary search tree is as follows:
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
#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
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