Binary Search Tree Implementation in C++
--
Binary search tree(BST) is a kind of binary tree(tree where each node has at most 2 child nodes) where any node of the tree will be less than all its right children and greater than all its left children. For Instance
To implement BST will implement three things that we can do on a BST:
- Insertion
- Search
- Deletion
Insertion
If we want to insert a value in our BST, let’s say we want to insert 17 . We will start from the root node, which in our case has the value 12. So, We will compare 12 and 17, as 12 is less than 17 we will go the right of the tree. The right node has the value 15 which is less than 17, so we go to the right node which is 16. Again, 16 is less than 17, so we go to the right node. But there is no node to the right of 16 and we will insert 17 there.
Search
To search any values in BST, we will do exactly what we did for insertion. For example, to search 11, we will compare 11 to 12 which is greater than 11, so we will go to left node(i.e 6), which is less than 11 so we go to the right node(i.e. 7) , again 7 is less than 11 so we go to the right node. But there is no right node, so we return false because, 11 is not in this BST.
Deletion
If we want to delete a node which doesn’t have any children node, we first do searching for that node then remove it and make it’s parent node to point to NULL. And if we want to delete a node which has only one child, we can search that and remove that node and make it’s child node point to the parent node of the removed node. But if we want to remove a node which has two children node, for instance- if we want to remove 12 then we have to take the smallest value in right sub-tree, which is 13 in our case and we will delete 12 and replace it with 13 and make parent of 13 point to NULL. Because any value that is smallest in right sub-tree will be greater than all the left values and less than all the values of the right sub-tree.
Code Implementation
Complexity:
time O(log(n)) | space O(1) for average case
time O(n) | space O(1) for worst case
The average case has O(log(n)) because, for insertion, searching and deletion we are not exploring every node, we are either exploring left or right sub tree and we are eliminated half of the tree every time. So, that’s why time complexity is log(n).
The reason the worst case is O(n) is if we have tree that doesn’t have only left sub-tree or only right sub-tree, we can’t eliminate half of the tree and we end up exploring the full tree. For instance
Space complexity is O(1) because we are only using one BST type variable currentNode and not storing anything in call stack(i.e. if we have implemented recursive solution).