Hello! Welcome back.
In our last lesson, we explored the structure of binary trees and implemented the three fundamental recursive traversal algorithms: pre-order, in-order, and post-order. We saw how the order of visiting the root and its subtrees leads to different, useful node sequences.
Today, we'll build directly on that knowledge by introducing a special constraint to the binary tree, transforming it into a Binary Search Tree (BST). This simple rule unlocks powerful efficiencies. Your goal for this lesson is to implement a Binary Search Tree with insert, search, and delete operations. Mastering the BST is a critical step toward an "architectural mindset," as it's the foundational concept behind many indexing systems in databases and other large-scale storage solutions.
1. The Binary Search Tree Property
A Binary Search Tree is a binary tree with a specific ordering property that must hold true for every node in the tree:
- All keys in the node's left subtree must be less than the node's key.
- All keys in the node's right subtree must be greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
This property is the key to the BST's efficiency.
To see a clear explanation of this core principle, the following video provides an excellent summary.
Binary Search Trees: Samuel's tutorial
The video 'Binary Search Trees: Samuel's tutorial' begins with a concise and formal definition of the BST property. It's a great starting point for our lesson.
Watch the segment from 02:06 to 03:17. Focus on how the property applies not just to the root but to every node in the tree.
The standard implementation of a BST uses a Node class similar to the one from our last lesson, typically containing the data (or key) and pointers to the left and right children.
2. Search Operation
The BST property makes searching for a value extremely efficient. The algorithm is straightforward:
- Start at the root.
- Compare the target value with the current node's key.
- If they match, you've found the node.
- If the target is less than the current node's key, move to the left child.
- If the target is greater than the current node's key, move to the right child.
- Repeat step 2 until the node is found or you reach a
nullpointer (which means the value is not in the tree).
This process effectively eliminates half of the remaining tree at each step in a well-balanced tree.
Binary Search Trees Time Complexity
The article 'Binary Search Trees Time Complexity' from Naukri Code 360 provides a clear, text-based explanation of the search algorithm, complete with a Python code example.
Read the 'Search Operation' section. Notice how the recursive logic directly follows the BST property.
As the article mentions, the time complexity of a search is , where is the height of the tree. In the next lesson, we'll dive deeper into what this means for balanced versus unbalanced trees.
3. Insert Operation
Inserting a new node follows almost the same logic as searching.
- Traverse the tree as if you were searching for the value you want to insert.
- When you reach a
nullpointer, you've found the correct position. - Insert the new node at that position.
This ensures the BST property is maintained.
Binary Search Trees: Samuel's tutorial
Let's return to Samuel Albanie's tutorial to see a detailed, step-by-step walkthrough of the insertion process.
Watch the segment on insertion from 10:35 to 12:53. Pay attention to how the algorithm descends the tree to find the correct leaf position to attach the new node.
Like searching, the time complexity for insertion is also .
Test your understanding!
Imagine you start with an empty Binary Search Tree and insert the following numbers in order: 8, 3, 10, 1, 6, 14, 4, 7, 13.
- Draw the final BST.
- Trace the path you would take to search for the number
6.
Show answer
-
Final BST:
8 / \ 3 10 / \ \ 1 6 14 / \ / 4 7 13 -
Path to search for
6:- Start at
8.6 < 8, so go left. - Current node is
3.6 > 3, so go right. - Current node is
6.6 == 6, so the node is found.
- Start at
4. Delete Operation
Deletion is the most complex operation because we must ensure the BST property is preserved after the node is removed. There are three cases to consider:
Case 1: The node to be deleted is a leaf (has no children).
This is the simplest case. You can simply remove the node by setting its parent's corresponding child pointer to null.
Case 2: The node to be deleted has one child.
This is also straightforward. You replace the node with its only child by linking the node's parent directly to the node's child.
Case 3: The node to be deleted has two children.
This is the most involved case. We can't simply remove the node, as that would leave two orphaned subtrees. The standard solution is:
- Find the node's in-order successor. This is the smallest node in the right subtree (the node you'd visit immediately after the current one in an in-order traversal).
- Copy the key of the in-order successor to the node you want to delete.
- Recursively call the delete function to remove the in-order successor from its original position.
Because the in-order successor is the smallest element in a subtree, it can have at most one (right) child. Therefore, deleting it will always fall under Case 1 or Case 2.
The following resource gives an excellent conceptual and visual breakdown of these three cases.
Binary Search Trees: Samuel's tutorial
Samuel Albanie's video provides a very thorough explanation of the deletion logic, including the trickiest case involving a node with two children.
Watch the detailed segment on deletion from 12:53 to 16:45. Focus on the logic for the four scenarios presented (cases 1, 2, and the two variations of case 3). This is the most complex part of the lesson, so feel free to re-watch it.
The time complexity for deletion is, again, , as it relies on searching for the node and its successor.
5. Implementation in Code
Now that you understand the algorithms for search, insert, and delete, it's time to see how they look in code. The article below provides complete, well-commented implementations in several languages, including Python and Java.
The article 'Binary Search Tree(BST)' from Programiz provides clear explanations and full code examples that tie all these operations together. This is a great reference for your own implementation.
First, review the 'Search Operation', 'Insert Operation', and 'Deletion Operation' sections to reinforce the concepts. Then, scroll down to the 'Python, Java and C/C++ Examples' section and study the implementation in your preferred language. Pay close attention to how the recursive deleteNode function handles the three cases.
Your task now is to take these concepts and implement a BinarySearchTree class yourself. You can use the provided examples as a guide, but try to write the code from your understanding of the algorithms.
Conclusion
In this lesson, you've taken the general concept of a binary tree and specialized it into the highly efficient Binary Search Tree. This structure is a fundamental building block in computer science, especially for systems requiring fast lookups on sorted data.
Key Takeaways:
- A Binary Search Tree maintains a strict ordering property:
left < root < right. - This property allows for efficient search and insert operations, which traverse the tree logarithmically in the average case.
- Deletion is the most complex operation, involving three cases depending on the number of children the node has. The two-child case is handled by finding the in-order successor.
- All three core operations—
search,insert, anddelete—have a time complexity of , where is the height of the tree.
In our next lesson, we will directly address the implications of that complexity. We will analyze the time complexity of BST operations in balanced vs. unbalanced scenarios, which will highlight why a simple BST can sometimes perform no better than a linked list and set the stage for understanding self-balancing trees like AVL and Red-Black trees.