BST insertion places a new key in the position determined by repeated comparisons, while deletion removes a node and reconnects its remaining structure without violating the binary search tree ordering property.
Overview
Insertion and deletion are dynamic BST operations that add or remove keys while preserving the ordering relationship between every node and its left and right subtrees.
Key concepts
name: Core idea; description: The central focus of insertion and deletion in bsts is the capability described here: BST insertion places a new key in the position determined by repeated comparisons, while deletion removes a node and reconnects its remaining structure without violating the binary search tree ordering property.; name: Problem context; description: Insertion and Deletion in BSTs is relevant when a computational task requires the behavior or capability described by this topic.; name: Correct use; description: Before using insertion and deletion in bsts, check its assumptions, input requirements, expected output, and resource constraints.
Complexity
balancedTree: O(log n) for insertion and deletion in a balanced BST.; degenerateTree: O(n) in the worst case for an unbalanced BST.; auxiliarySpace: O(h) for recursive implementations and O(1) auxiliary space for iterative implementations that use parent references or track the required links.
Example
For a BST containing 50 as the root, 30 and 70 as children, and 20, 40, 60, and 80 as leaves, deleting 30 requires handling the two-child case. Its inorder successor is 40, which can replace 30 while preserving the BST ordering property.
Applications
Maintaining ordered records.; Implementing dynamic dictionaries.; Building ordered sets.; Updating in-memory search structures.; Maintaining values that need predecessor and successor queries.
Limitations
The suitability of insertion and deletion in bsts depends on the exact problem requirements and the assumptions made about the input.; An implementation of insertion and deletion in bsts can fail if its boundary conditions, data representation, or required invariants are handled incorrectly.; For insertion and deletion in bsts, evaluate representative and unusually difficult inputs; a single small demonstration is not enough to establish reliability.
Common mistakes
Deleting a node with one child without reconnecting its child.; Using an arbitrary replacement key in the two-child case.; Failing to remove the successor or predecessor from its original position.; Forgetting to update the root.; Assuming insertion automatically keeps the tree balanced.
For a BST containing 50 as the root, 30 and 70 as children, and 20, 40, 60, and 80 as leaves, deleting 30 requires handling the two-child case. Its inorder successor is 40, which can replace 30 while preserving the BST ordering property.
Insertion
Definition
Insertion adds a new key at the appropriate leaf position after following the BST comparison rules from the root.
Algorithm
Begin at the root.
Compare the new key with the current node.
Move left when the new key is smaller.
Move right when the new key is larger.
Continue until the appropriate null child position is reached.
Create and attach the new node at that position.
Apply the implementation's duplicate-key policy if an equal key is encountered.
Pseudocode
INSERT(root, key):
if root == null:
return new Node(key)
if key < root.key:
root.left = INSERT(root.left, key)
else if key > root.key:
root.right = INSERT(root.right, key)
return root
Example
Insert 65 into a BST with root 50, right child 70, and left child 60. The comparisons lead right from 50, left from 70, and then right from 60, so 65 is inserted as the right child of 60.
Complexity
O(h), where h is the tree height.
Deletion
Definition
Deletion removes a specified key while preserving the BST ordering property.
Three Cases
| Case | Description |
|---|
Leaf Node | A node with no children can be removed directly by changing its parent's corresponding child reference to null. |
One Child | The node is removed and its only child is connected directly to its parent. If the node is the root, its child becomes the new root. |
Two Children | The node is replaced using its inorder successor or inorder predecessor. The successor is the minimum key in the right subtree; the predecessor is the maximum key in the left subtree. The replacement node is then removed from its original position. |
Successor Method
A common approach for deleting a node with two children is to copy or move the inorder successor's key into the target position, then delete the successor from the right subtree. The successor has no left child, so its removal is simpler.
Predecessor Method
Alternatively, the inorder predecessor can be used. It is the maximum key in the left subtree and has no right child.
Root Deletion
Deleting the root requires updating the root reference. The new root may be null, its only child, or a replacement chosen from one of its subtrees.
Pseudocode Concept
Find the target node, identify its number of children, apply the corresponding deletion case, and reconnect the affected parent and child references.
Complexity
O(h), because finding the node and its replacement requires following paths whose lengths depend on the tree height.
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.