A binary Search tree is a type of binary tree. However, there are some rules for a binary tree to become a binary search tree.
- The right child of the node must always be greater than the parent node.
Here, the right child node 85, is greater than the parent node 50.
2. The left child of the node must be less than the parent node.
Here, the left child node 23 is less than parent node 50.
As a binary search tree is a binary tree, a node can only have a maximum of 2 children.Let’s see an example of a binary tree.
Searching an element in binary tree
A binary tree is great when it comes to searching. Let’s see why.
Suppose, we are searching for value 34 in the binary tree.
Here’s how we do it.
First, the root node is checked.
The root node is not 34.
Now, we check if 34 is greater or less than the root node.
As 34 is less than root node 50. The left child node of 50 is checked.
Now, 34 is compared to 23, as 34 is greater than 23 the right node is checked.
The right node of 23 is 34. So, we have found the node we are looking for and the search ends.
As you can see, we don’t have to traverse every node to search a node. So, the searching is easy and the time complexity is O(logN) which is very much efficient.
Inserting in Binary Search tree
Suppose, we want to insert 29 in the tree.
First, we check if 29 is greater than or less than the root node. As it is less, now we traverse to the left node. Now, we will check if 29 is greater or less than 23, as it is greater we traverse to the right. Now, we will check if 29 is great or less than 34. As it is less, now we finally insert the node as the left child node of node 34.
In this way, only a limited number of nodes have been visited, so the time complexity is O(logN).