by A Binary Search Tree is a Binary tree in which all the nodes has following properties.
- Left subtree of a node contains all the nodes having values lesser than the node.
- Right subtree of a node contains all the nodes having values higher than the node.
- Both the left and right subtree is also a Binary Search Tree.
As the name suggests, this data structure is mainly used for faster searching. In order to do that, restrictions are applied while inserting/deleting an element into the tree. As a result of these restrictions, worst case search time complexity remains at O(log n). Before going ahead have a look into Binary Search Tree basics.
Binary Search Tree Implementation
Here we are going to talk about a very simple implementation of Binary Search tree using Linked List similar data structure. Also we will discuss about Insertion operation in Binary Search Tree.
Before looking into Insertion operation detail let’s look into basic C++ class definition for Binary Search Tree.
template <typename T>
class BinarySearchTree
{
public:
T m_data;
BinarySearchTree* m_left;
BinarySearchTree* m_right;
BinarySearchTree (T data);
~BinarySearchTree ();
};
Binary Search Tree Class Function Implementation
Let’s have a look into all the functions/operations definition of Binary Search Tree Class.
Constructor/Destructor implementation
/* This constructor will be called when an isolated node is created */
template <typename T>
BinarySearchTree<T>::BinarySearchTree(T data): m_data(data),
m_left (NULL),
m_right (NULL)
{}
/* No dynamic allocation is being done, hence nothing to delete here */
template <typename T>
BinarySearchTree<T>::~BinarySearchTree ()
{}
Inserting an element
In order to insert an element in a Binary Search Tree, first we need to find a place for this new element and then we need to add the element at that specific place.
Note that, after inserting any element in Binary Search Tree, it’s property must be retained.
As shown in above diagram, if insertion of new elements done at a particular place then Binary Search Tree properties are still holding correctly. In this article we will look into methods for inserting an element into Binary Search Tree.
Algorithm
- Start from the root. If root is empty is then put the node as root.
- If new node data is higher than root node value then go towards right child of the root else traverse towards left child.
- If there is no child present then add the new node there else repeat step 2 and step 3.
Insertion operation can be implemented in both iterative and recursive manner.
Inserting an element using iterations
Let’s look into the sample code.
/* Below function will be used when new node needs to be created */
template <typename T>
void insert_element_in_bst (T data, BinarySearchTree<T>* root)
{
BinarySearchTree<T>* new_node = new BinarySearchTree<T> (data);
insert_node_in_bst (new_node, root);
}
/* Below function will be used when new node is already created */
template <typename T>
void insert_node_in_bst (BinarySearchTree<T>* new_node, BinarySearchTree<T>* root)
{
BinarySearchTree<T>* temp = root;
if (!temp)
{
cout << "BST is empty !!!" << endl;
return;
}
while (temp)
{
if (new_node -> m_data > temp -> m_data)
{
if (!temp -> m_right)
{
temp -> m_right = new_node;
break;
}
temp = temp -> m_right;
}
else
{
if (!temp -> m_left)
{
temp -> m_left = new_node;
break;
}
temp = temp -> m_left;
}
}
}
Inserting an element using recursion
Let’s look into the sample code.
template <typename T>
void insert_element_in_bst_recursive (T data, BinarySearchTree<T>* root)
{
BinarySearchTree<T>* new_node = new BinarySearchTree<T> (data);
insert_node_in_bst_recursive (new_node, root);
}
template <typename T>
void insert_node_in_bst_recursive (BinarySearchTree<T>* new_node, BinarySearchTree<T>* root)
{
BinarySearchTree<T>* temp = root;
if (!temp)
{
cout << "BST is empty !!!" << endl;
return;
}
if (new_node -> m_data > temp -> m_data)
{
if (!temp -> m_right)
{
temp -> m_right = new_node;
return;
}
insert_node_in_bst_recursive (new_node, temp -> m_right);
}
else
{
if (!temp -> m_left)
{
temp -> m_left = new_node;
return;
}
insert_node_in_bst_recursive (new_node, temp -> m_left);
}
}
Let’s look into the sample main function which utilizes Binary Search Tree class definition and iterative functions defined above.
template <typename T>
void print_binary_tree_inorder (BinarySearchTree<T>* root)
{
if (root -> m_left)
print_binary_tree_inorder (root -> m_left);
cout << " " << root -> m_data;
if (root -> m_right)
print_binary_tree_inorder (root -> m_right);
}
template <typename T>
void print_tree (BinarySearchTree<T>* root)
{
cout << "Binary tree contents: ";
print_binary_tree_inorder (root);
cout << endl;
}
/* Simply used this function to delete all nodes and free memory */
template <typename T>
void delete_all_nodes (BinarySearchTree<T>* root)
{
if (!root)
return;
if (root -> m_left)
{
delete_all_nodes (root -> m_left);
}
if (root -> m_right)
{
delete_all_nodes (root -> m_right);
}
delete root;
}
int main ()
{
BinarySearchTree<int>* root = new BinarySearchTree<int> (33);
insert_element_in_bst (20, root);
insert_element_in_bst (10, root);
insert_element_in_bst (30, root);
insert_element_in_bst (40, root);
insert_element_in_bst (50, root);
insert_element_in_bst (43, root);
insert_element_in_bst (77, root);
insert_element_in_bst (69, root);
insert_element_in_bst (25, root);
insert_element_in_bst (11, root);
insert_element_in_bst (10, root);
insert_element_in_bst (5, root);
insert_element_in_bst (18, root);
insert_element_in_bst (67, root);
insert_element_in_bst (88, root);
insert_element_in_bst (99, root);
insert_element_in_bst (65, root);
insert_element_in_bst (58, root);
insert_element_in_bst (51, root);
insert_element_in_bst (77, root);
print_tree (root);
delete_all_nodes (root);
}
Let’s analyze the output of this main function.
Binary tree contents: 5 10 10 11 18 20 25 30 33 40 43 50 51 58 65 67 69 77 77 88 99
Let’s look into the sample main function which utilizes Binary Search Tree class definition and recursive functions defined above.
int main ()
{
BinarySearchTree<int>* root = new BinarySearchTree<int> (33);
insert_element_in_bst_recursive (20, root);
insert_element_in_bst_recursive (10, root);
insert_element_in_bst_recursive (30, root);
insert_element_in_bst_recursive (40, root);
insert_element_in_bst_recursive (50, root);
insert_element_in_bst_recursive (43, root);
insert_element_in_bst_recursive (77, root);
insert_element_in_bst_recursive (69, root);
insert_element_in_bst_recursive (25, root);
insert_element_in_bst_recursive (11, root);
insert_element_in_bst_recursive (10, root);
insert_element_in_bst_recursive (5, root);
insert_element_in_bst_recursive (18, root);
insert_element_in_bst_recursive (67, root);
insert_element_in_bst_recursive (88, root);
insert_element_in_bst_recursive (99, root);
insert_element_in_bst_recursive (65, root);
insert_element_in_bst_recursive (58, root);
insert_element_in_bst_recursive (51, root);
insert_element_in_bst_recursive (77, root);
print_tree (root);
delete_all_nodes (root);
}
Let’s analyze the output of this main function.
Binary tree contents: 5 10 10 11 18 20 25 30 33 40 43 50 51 58 65 67 69 77 77 88 99
