Insertion Operation
Inserting a new node into a Binary Search Tree involves finding the appropriate position to maintain the BST property. The insertion process starts at the root node & compares the value of the new node with the current node's value. If the new value is smaller, it proceeds to the left subtree, & if it is greater, it moves to the right subtree. This process continues recursively until a null node is reached, indicating the position where the new node should be inserted. The new node is then added as the left or right child of the last visited node, depending on its value.
For example :
def insert(self, value):
if value < self.value:
if self.left is None:
self.left = Node(value)
else:
self.left.insert(value)
else:
if self.right is None:
self.right = Node(value)
else:
self.right.insert(value)
The insertion operation has a time complexity of O(log n) in the average & best cases, similar to the search operation. This is because the insertion follows the same path as the search to find the appropriate position for the new node. However, in the worst case, when the BST is skewed, the time complexity becomes O(n) as the insertion may need to traverse all the nodes to find the correct position.
It's important to note that the insertion operation does not guarantee a balanced BST. Depending on the order of insertions, the BST may become skewed, leading to decreased performance. To maintain a balanced BST, self-balancing techniques like AVL trees or Red-Black trees can be used.
Deletion Operation
Deleting a node from a Binary Search Tree is a more complex operation compared to search & insertion. The deletion process involves three main cases:
1. Deleting a leaf node (node with no children):
- Simply remove the node from its parent.
2. Deleting a node with one child:
- Replace the node with its child & update the parent's reference.
3. Deleting a node with two children:
- Find the minimum value in the right subtree (or maximum value in the left subtree) of the node to be deleted.
- Replace the node's value with the minimum (or maximum) value.
- Delete the minimum (or maximum) value node from the right (or left) subtree.
For example :
def delete(self, value):
if value < self.value:
if self.left:
self.left = self.left.delete(value)
elif value > self.value:
if self.right:
self.right = self.right.delete(value)
else:
if self.left is None:
return self.right
elif self.right is None:
return self.left
else:
min_node = self.right.find_min()
self.value = min_node.value
self.right = self.right.delete(min_node.value)
return self
def find_min(self):
if self.left is None:
return self
else:
return self.left.find_min()
The deletion operation has a time complexity of O(log n) in the average & best cases, as it involves searching for the node to be deleted & then performing the necessary operations based on the case. However, in the worst case, when the BST is skewed, the time complexity becomes O(n) because the search & deletion may need to traverse all the nodes.
Deleting a node from a BST may lead to an unbalanced tree, similar to the insertion operation. Self-balancing techniques can be employed to maintain the balance of the BST after deletion.
Time & Space Complexity for Each Operation
1. Search Operation
-> Time Complexity:
- Average & Best Case: O(log n)
- Worst Case: O(n)
-> Space Complexity: O(1) as it uses constant extra space for the search operation.
2. Insertion Operation
-> Time Complexity:
- Average & Best Case: O(log n)
- Worst Case: O(n)
-> Space Complexity: O(1) as it uses constant extra space for the insertion operation.
3. Deletion Operation
-> Time Complexity:
- Average & Best Case: O(log n)
- Worst Case: O(n)
-> Space Complexity: O(1) as it uses constant extra space for the deletion operation.
It's important to note that the time complexity of BST operations depends on the height of the tree. In a balanced BST, the height is logarithmic, resulting in efficient operations. However, in the worst case, when the BST is skewed & resembles a linked list, the height becomes linear, leading to a time complexity of O(n) for all operations.
The space complexity of BST operations is O(1) because they modify the tree in-place & do not require any additional data structures that grow with the input size. The space used by the BST itself is not considered as extra space in the context of space complexity analysis.
Frequently Asked Questions
Can a BST contain duplicate values?
No, a standard BST does not allow duplicate values to maintain its property. However, variations like multi-sets or multi-maps can be used to handle duplicates.
Is a BST always balanced?
No, a BST is not always balanced. The balance depends on the order of insertions & deletions. Self-balancing techniques like AVL trees or Red-Black trees can be used to maintain balance.
Can a BST be used for range queries?
Yes, BSTs can efficiently support range queries. By traversing the tree in-order, nodes within a given range can be retrieved in O(log n + k) time, where k is the number of nodes in the range.
Conclusion
In this article, we have learned about Binary Search Trees (BSTs) & their fundamental operations: search, insertion, & deletion. We discussed the time & space complexity of each operation, which highlights the efficiency of BSTs in the average & best cases. However, we also noted that BSTs can become unbalanced, leading to decreased performance in the worst case.
You can also check out our other blogs on Code360.
7+ registered 
