Before getting into the Binary Search Tree (BST), you have to know the basics of Tree and Binary Tree. I assume that you have the basic idea of Tree and Binary Tree.
Intro
A Binary Search Tree is a special type of Binary Tree with some extra conditions. In a binary tree, a node can have at most two children. And in a Binary Search Tree, a node can have at most two children, and also its left subtree has to be smaller, and the right subtree has to be greater.
In computer science, a binary search tree, also called an ordered or sorted binary tree, is a rooted binary tree data structure whose internal nodes each store a key greater than all the keys in the node’s left subtree and less than those in its right subtree.
Wikipedia
Suppose we have a binary tree of three nodes. Let’s see the following example.
Can we count the above Binary Tree as a Binary Search Tree? Yes, we can. Because the left child (1) is less than the root (2) and the right one (3) is greater.
If the value of the left child has become 5, we can call it a Binary Tree but not a Binary Search Tree. Cause the left child is greater than the root. It fails to meet the BST requirements.
Let’s see two more examples.
Look at the above two examples. Both are binary trees, but one is not valid BST. I hope you already figured out which one and why it’s not BST.
Example two is not a Binary Search Tree. Here, 12 is greater than 7, and as a right child/subtree, it’s okay if we count it from 7. But if we consider 12 as the left subtree’s node from the root. 12 is not smaller than the root. And that’s the reason it fails to meet the BST requirements. I hope you got the idea.
Now let’s see some operations in a Binary Search Tree.
Search
Search in BST is pretty straightforward.
We know the definition of BST. So it’s easier for us to decide where a node is located.
Let’s search for 7 in the above BST. Let’s start from the root node. Is the root node equal to 7? No, it’s not, and the searching value is less than 9. Then it must be in the left subtree of the root. So go to the left child. Now it’s 6, and it’s not equal to 7. And now the searching value is greater than 6. So it must be in the right subtree of 6. So go the right child of 6. And finally, the right child of 6 is 7! So we got our searching value this BST.
If no nodes are available for the search, we can say that the value is not in the BST.
There is a problem on LeetCode about searching in a BST. LeetCode 700. I wrote about this problem in my blog. Check it out.
Insert
Inserting a node in a BST is also easy. It’s almost similar to searching for a node in a BST. Let’s see the following BST.
Let’s insert 11 into the above BST. Let’s search for a valid place to insert it. First, we have to compare it with the root. As the root 9 is less than 11, the right subtree might be the best position to insert. Now, let’s compare 11 with the left child of the root. And this case, 11 is less than 15, and the left child of node 15 is null. So we can insert 11 as a left child of 15.
If there is no BST to insert 11, we can insert it as the root node.
There is a problem on LeetCode about inserting into a BST. LeetCode 701. I wrote about this problem in my blog. Check it out.
Delete
Deleting a node from a BST is a bit tricky. To delete a node, first, we need to search that node. If the node is found, we need to consider mainly three cases.
- If the node is a leaf node, we can delete it.
- If the node has one subtree, it could be left or right. Then we can replace it with its left or right subtree.
- If the node has both left and right subtree, find the minimum node from the right subtree, and replace it with the minimum node. And then, delete that minimum node from the right subtree.
Let’s see the visual for a better understanding.
There is the same problem in LeetCode. LeetCode 450. You can try to solve it.
Generally, the time complexity of these operations is O(h), where h is the height of a tree. But in the worst case, it might be O(n).
Final words
There is a lot to share about Binary Search Tree. I think you got a rapid overview of the Binary Search Tree from this blog.
