Insertion in Binary Search Tree
Introduction to Searching in BST
“Insertion in a Binary Search Tree is the process of adding a new node while maintaining the tree’s ordered structure.” We’ll explore the fundamental principles, insertion algorithms, and code examples in both recursive and iterative methods.
In this article, you dive deep into Insertion in Binary Search Tree with its code, methods and complexity of the method.
What is Insertion in Binary Search Tree(BST)?
Insertion in a Binary Search Tree (BST) is a fundamental operation that allows you to add new elements while maintaining the tree’s ordered structure. BSTs are hierarchical data structures known for their efficiency in searching, and the insertion process is crucial for building and maintaining these trees.
Example :
The Basics of Binary Search Tree
Before diving into the insertion process, let’s revisit the key characteristics of a Binary Search Tree:
Node Structure: Each node in a BST contains a value (or key) and two child nodes: a left child and a right child.
Ordering Property: The values in the left subtree of a node are less than or equal to the node’s value, while the values in the right subtree are greater than or equal to the node’s value.
Insertion Algorithm
The insertion algorithm in a BST is relatively straightforward:
Start at the root node.
Compare the value you want to insert with the value of the current node.
If the value is less than the current node’s value, move to the left subtree. If the value is greater, move to the right subtree.
Repeat steps 2 and 3 until you reach a null (empty) node.
At the null node, insert the new value as a new node, either as the left child (if the new value is less) or as the right child (if the new value is greater).
The insertion is complete.
Significance of Ordered Insertion in Binary Search Tree
BSTs rely on a critical ordering property: nodes to the left have smaller values, and nodes to the right have larger values than their parent node. Insertion respects this order, ensuring that the tree remains balanced and efficient for searching.
Recursive vs. Iterative Insertion
BSTs can be inserted into using both recursive and iterative methods. Recursive insertion is elegant and intuitive, while iterative insertion provides an efficient alternative. Our previous sections demonstrated both techniques.
Methods of Insertion in Binary Search Tree(BST)
-
Recursive Method
-
Iterative Method
1. Insertion in Binary Search Tree(BST) using Recursive method
class TreeNode:
def __init__(self, key):
self.val = key
self.left = None
self.right = None
def insert_bst(root, key):
if root is None:
return TreeNode(key)
if key < root.val:
root.left = insert_bst(root.left, key)
else:
root.right = insert_bst(root.right, key)
return root
if __name__ == "__main__":
# Create an initial BST:
root = TreeNode(50)
root.left = TreeNode(30)
root.right = TreeNode(70)
root.left.left = TreeNode(20)
root.left.right = TreeNode(40)
# Insert a new value (e.g., 60) into the BST:
new_value = 60
root = insert_bst(root, new_value)
Output :
In-order traversal of the updated BST: 20 30 40 50 60 70
Explanation
The provided Python code demonstrates the insertion of a new node into a Binary Search Tree (BST) using a recursive method. A TreeNode class defines the BST structure, and the insert_bst function handles the insertion process. It ensures that the BST’s ordered property is preserved: nodes with smaller values are placed to the left, and those with greater or equal values are placed to the right. An in-order traversal confirms the updated BST’s sorted order, as displayed in the example output.
2. Insertion in Binary Search Tree(BST) using Iterative method
class TreeNode:
def __init__(self, key):
self.val = key
self.left = None
self.right = None
def insert_bst(root, key):
new_node = TreeNode(key)
if root is None:
return new_node
current = root
while current:
parent = current
if key < current.val:
current = current.left
if current is None:
parent.left = new_node
else:
current = current.right
if current is None:
parent.right = new_node
return root
def inorder_traversal(root):
if root:
inorder_traversal(root.left)
print(root.val, end=" ")
inorder_traversal(root.right)
if __name__ == "__main__":
# Create an initial BST:
root = TreeNode(50)
root.left = TreeNode(30)
root.right = TreeNode(70)
root.left.left = TreeNode(20)
root.left.right = TreeNode(40)
# Insert a new value (e.g., 55) into the BST:
new_value = 55
root = insert_bst(root, new_value)
# Verify the updated BST with an in-order traversal:
print("In-order traversal of the updated BST:")
inorder_traversal(root)
Output :
In-order traversal of the updated BST: 20 30 40 50 55 70
Explanation
The code showcases iterative insertion of a new node (with the value 55) into a Binary Search Tree (BST). It utilizes an iterative method to traverse the tree and maintain the BST’s ordered structure. An in-order traversal confirms the sorted order of the updated BST. The example output demonstrates the BST’s elements, including the newly inserted value.
Complexity Analysis of Insertion
Real World Application of Insertion in Binary Search Tree
Insertion in Binary Search Trees (BSTs) has numerous real-world applications across various domains due to its efficient ordered data storage and retrieval capabilities. Some prominent real-world applications include:
Databases: BSTs are used in database management systems for indexing. Database records are organized in a structured manner within BSTs based on their keys (e.g., primary keys). This allows for efficient data retrieval, sorting, and searching.
Symbol Tables in Compilers: Compilers and interpreters use symbol tables, which are often implemented as BSTs. These symbol tables store variable names, function names, and other identifiers, enabling quick look-up and management during the compilation process.
File Systems: File systems often use BSTs for maintaining the hierarchical structure of directories and files. Directory trees are structured using BSTs, simplifying operations like file retrieval and traversal.
- Geographic Information Systems (GIS): In GIS applications, spatial data can be organized using BSTs to efficiently query and retrieve geographic features, such as locations, maps, and spatial attributes.
To wrap it up:
Insertion in a Binary Search Tree is a crucial operation that allows you to maintain the tree’s ordered structure. Whether you’re building a BST from scratch or adding elements dynamically, understanding the insertion process is key to harnessing the efficiency of BSTs for ordered data storage and retrieval.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Question 1.
How does Insertion Maintain the Ordered Property of a BST?
Insertion ensures that the hierarchy of the BST is maintained. New elements are compared to existing nodes, and they are placed as child nodes accordingly, ensuring that smaller values are on the left, and larger values are on the right.
Question 2.
What Happens If I Insert a Duplicate Value into a BST?
In most BST implementations, duplicates are typically allowed. The behavior may vary depending on the specific implementation. Some may store duplicates in a separate data structure, while others may allow duplicates in the same tree.
Question 3.
Can a BST Become Unbalanced After Multiple Insertions?
Yes, if insertions are not performed carefully, a BST can become unbalanced, resembling a linked list. To maintain balance, self-balancing BSTs, like AVL trees, automatically adjust their structure during insertions.
Question 4.
Are There Any Special Cases or Rules for Root Node Insertion?
In some BST implementations, the root node may be handled differently during insertion. In others, it follows the same insertion rules as any other node.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment